The Little Elephant has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai.

The Little Elephant wants to count, how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = a1a2... alarar + 1... an has no more than k inversions. 

An inversion in sequence b is a pair of elements of the sequence b, that change their relative order after a stable sorting of the sequence. In other words, an inversion is a pair of integers i and j, such that 1 ≤ i < j ≤ |b| and bi > bj, where |b| is the length of sequence b, and bj is its j-th element.

Help the Little Elephant and count the number of the described pairs.

Input

The first line contains two integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ 1018) — the size of array a and the maximum allowed number of inversions respectively. The next line contains n positive integers, separated by single spaces, a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of array a.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output

In a single line print a single number — the answer to the problem.

Examples

Input

3 1
1 3 2


Output

3


Input

5 2
1 3 2 1 7


Output

6
#include <bits/stdc++.h>
using namespace std;
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
long long toInt64(string s) {
  long long r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
double toDouble(string s) {
  double r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
string toString(long long n) {
  string s, s1;
  while (n / 10 > 0) {
    s += (char)((n % 10) + 48);
    n /= 10;
  }
  s += (char)((n % 10) + 48);
  n /= 10;
  s1 = s;
  for (int i = 0; i < s.length(); i++) s1[(s.length() - 1) - i] = s[i];
  return s1;
}
bool isUpperCase(char c) { return c >= 'A' && c <= 'Z'; }
bool isLowerCase(char c) { return c >= 'a' && c <= 'z'; }
bool isLetter(char c) { return c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z'; }
bool isDigit(char c) { return c >= '0' && c <= '9'; }
char toLowerCase(char c) { return (isUpperCase(c)) ? (c + 32) : c; }
char toUpperCase(char c) { return (isLowerCase(c)) ? (c - 32) : c; }
long long gcd(long long a, long long b) {
  if (!a) return b;
  return gcd(b % a, a);
}
int x[100001];
int n;
const int MAXN = 100001;
struct fenwick {
  long long fen[100001];
  int get(int andis) {
    if (andis == 0) return 0;
    return fen[andis] + get(andis - (andis & (-andis)));
  }
  void add(int x, int val) {
    for (; x <= MAXN; x += x & -x) fen[x] += val;
  }
  void clear() { fill(fen, fen + MAXN, 0); }
};
long long L[100001], R[100001];
fenwick F;
fenwick fL, fR;
map<int, int> MAP;
int y[MAXN];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> x[i], y[i] = x[i];
  sort(y, y + n);
  for (int i = 1; i <= n; i++)
    if (MAP[y[i - 1]] == 0) MAP[y[i - 1]] = i;
  L[0] = 0;
  F.add(MAP[x[0]], 1);
  for (int i = 1; i < n; i++) {
    L[i] = L[i - 1];
    F.add(MAP[x[i]], 1);
    L[i] += (i + 1) - F.get(MAP[x[i]]);
  }
  F.clear();
  R[n - 1] = 0;
  F.add(MAP[x[n - 1]], 1);
  for (int i = n - 2; i >= 0; i--) {
    R[i] = R[i + 1];
    F.add(MAP[x[i]], 1);
    R[i] += F.get(MAP[x[i]] - 1);
  }
  long long cnt = 0;
  int l = 0, r = 1;
  for (int i = 1; i < n; i++) fR.add(MAP[x[i]], 1);
  fL.add(MAP[x[0]], 1);
  long long ans = 0;
  fR.add(MAP[x[0]], 1);
  cnt += fR.get(MAP[x[0]] - 1);
  cnt += L[0] + R[1];
  fR.add(MAP[x[0]], -1);
  while (l < n && r < n) {
    int tmpR = r, tmpL = l;
    if (cnt <= k) {
      ans += n - r;
      l++;
      if (l == r) {
        fR.add(MAP[x[r]], -1);
        fL.add(MAP[x[r]], 1);
        cnt -= (l + 2) - fL.get(MAP[x[r]]);
        fL.add(MAP[x[r]], -1);
        r++;
      }
      fL.add(MAP[x[l]], 1);
      fR.add(MAP[x[l]], 1);
      cnt += fR.get(MAP[x[l]] - 1);
      fR.add(MAP[x[l]], -1);
    } else {
      fR.add(MAP[x[r]], -1);
      fL.add(MAP[x[r]], 1);
      cnt -= (l + 2) - fL.get(MAP[x[r]]);
      fL.add(MAP[x[r]], -1);
      r++;
    }
    cnt -= L[tmpL] + R[tmpR];
    cnt += L[l] + R[r];
  }
  cout << ans << endl;
}
