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;
using ll = long long;
using ld = double;
const int mxn = 1e5 + 10;
const int inf = 1e9;
int n, a[mxn];
ll pref[mxn], suff[mxn];
ll k;
class Segtree {
 public:
  int t[2 * mxn];
  int N = mxn;
  Segtree() {
    for (int i = 0; i < 2 * mxn; i++) t[i] = 0;
  }
  void inc(int p, int val) {
    p += N;
    t[p] += val;
    p /= 2;
    for (; p >= 1; p >>= 1) t[p] = t[p << 1] + t[p << 1 | 1];
  }
  int ask(int l, int r) {
    if (l > r) return 0;
    l += N, r += N;
    int ret = 0;
    for (; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) ret += t[l];
      if (!(r & 1)) ret += t[r];
      l++;
      r--;
    }
    return ret;
  }
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  vector<int> vals;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    vals.push_back(a[i]);
  }
  map<int, int> f;
  int cnt = 0;
  sort(begin(vals), end(vals));
  for (int x : vals) {
    if (!f.count(x)) f[x] = cnt++;
  }
  for (int i = 1; i <= n; i++) a[i] = f[a[i]];
  Segtree pref_cnt;
  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + pref_cnt.ask(a[i] + 1, pref_cnt.N - 1);
    pref_cnt.inc(a[i], 1);
  }
  Segtree suff_cnt;
  for (int i = n; i >= 1; i--) {
    suff[i] = suff[i + 1] + suff_cnt.ask(0, a[i] - 1);
    suff_cnt.inc(a[i], 1);
  }
  ll ans = 0;
  int l = 0;
  ll cur_inv = suff[2];
  Segtree L, R;
  for (int i = 2; i <= n; i++) R.inc(a[i], 1);
  for (int r = 2; r <= n; r++) {
    while (l + 1 < r and
           cur_inv + R.ask(0, a[l + 1] - 1) + L.ask(a[l + 1] + 1, L.N - 1) <=
               k) {
      cur_inv += R.ask(0, a[l + 1] - 1) + L.ask(a[l + 1] + 1, L.N - 1);
      L.inc(a[l + 1], 1);
      l++;
    }
    ans += l;
    R.inc(a[r], -1);
    cur_inv -= R.ask(0, a[r] - 1);
    cur_inv -= L.ask(a[r] + 1, L.N - 1);
  }
  cout << ans << '\n';
  return 0;
}
