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;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O0")
#pragma GCC optimize("O1")
long long pw(int a, int b) {
  long long ret = 1;
  long long mul = a;
  while (b > 0) {
    if (b & 1) ret *= mul;
    mul *= mul;
    b /= 2;
  }
  return ret;
}
long long to_int(string s) {
  long long ret = 0;
  for (int(i) = (0); (i) < (s.size()); (i)++) {
    ret += pw(10, s.size() - i - 1) * (long long)(s[i] - '0');
  }
  return ret;
}
const int MAXN = 1e5 + 15;
int a[MAXN], b[MAXN], bit[2][MAXN], n, p1, p2 = 1;
long long k, ans, inv;
void upd(int r, int d, int t) {
  for (; r < n; r |= (r + 1)) bit[t][r] += d;
}
int get(int r, int t) {
  int ret = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[t][r];
  return ret;
}
int main() {
  cin >> n >> k;
  for (int(i) = (0); (i) < (n); (i)++) cin >> a[i], b[i] = a[i];
  sort(b, b + n);
  map<int, int> key;
  int cur = 1;
  for (int(i) = (0); (i) < (n); (i)++)
    if (key[b[i]] == 0) key[b[i]] = cur++;
  for (int(i) = (0); (i) < (n); (i)++) a[i] = key[a[i]] - 1;
  for (int(i) = (0); (i) < (n); (i)++) {
    inv += i - (i > 0) - get(a[i], 1) + (i && a[0] > a[i]);
    upd(a[i], 1, (i > 0));
  }
  while (p2 < n - 1 or p1 < n - 2) {
    if (inv <= k and p1 < p2 - 1) {
      ans += n - p2;
      p1++;
      inv += get(a[p1] - 1, 1) + p1 - get(a[p1], 0);
      upd(a[p1], 1, 0);
    } else {
      if (p2 == n - 1) break;
      if (inv <= k) ans++;
      inv -= get(a[p2] - 1, 1) + p1 + 1 - get(a[p2], 0);
      upd(a[p2], -1, 1);
      p2++;
    }
  }
  ans += (inv <= k);
  cout << ans << "\n";
}
