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;
const long long maxn = 2e5 + 10;
long long ans3, sum2[maxn], ans1, a[maxn], ans, val[maxn], sum[maxn * 4], k, n,
    sum1[maxn * 4];
map<long long, bool> mp;
pair<long long, long long> q[maxn];
vector<long long> v;
void change(long long pos, long long x, long long id = 1, long long s = 0,
            long long e = v.size()) {
  if (s + 1 == e) {
    sum[id] += x;
    return;
  }
  long long mid = (s + e) / 2;
  if (pos < mid)
    change(pos, x, id << 1, s, mid);
  else
    change(pos, x, id << 1 | 1, mid, e);
  sum[id] = sum[id << 1] + sum[id << 1 | 1];
}
long long get(long long l, long long r, long long id = 1, long long s = 0,
              long long e = v.size()) {
  if (e <= l || r <= s) return 0;
  if (l <= s && e <= r) return sum[id];
  long long mid = (s + e) / 2;
  return get(l, r, id << 1, s, mid) + get(l, r, id << 1 | 1, mid, e);
}
void change1(long long pos, long long x, long long id = 1, long long s = 0,
             long long e = n + 1) {
  if (s + 1 == e) {
    sum1[id] += x;
    return;
  }
  long long mid = (s + e) / 2;
  if (pos < mid)
    change1(pos, x, id << 1, s, mid);
  else
    change1(pos, x, id << 1 | 1, mid, e);
  sum1[id] = sum1[id << 1] + sum1[id << 1 | 1];
}
long long get1(long long l, long long r, long long id = 1, long long s = 0,
               long long e = n + 1) {
  if (e <= l || r <= s) return 0;
  if (l <= s && e <= r) return sum1[id];
  long long mid = (s + e) / 2;
  return get1(l, r, id << 1, s, mid) + get1(l, r, id << 1 | 1, mid, e);
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    if (mp[a[i]] == 0) {
      v.push_back(a[i]);
      mp[a[i]] = 1;
    }
    q[i].first = a[i];
    q[i].second = i;
  }
  v.push_back(0);
  v.push_back(1e10);
  sort(v.begin(), v.end());
  sort(q, q + n);
  for (long long i = 0; i < n; i++) {
    val[q[i].second] = get1(q[i].second + 1, n + 1);
    ans += val[q[i].second];
    change1(q[i].second, 1);
  }
  memset(sum1, 0, sizeof sum1);
  for (long long i = n - 1; i >= 0; i--) {
    val[q[i].second] += get1(0, q[i].second + 1);
    change1(q[i].second + 1, 1);
  }
  long long l1 = 0, r1 = 1;
  sum2[0] = val[0];
  while (l1 != r1) {
    if (k >= ans + ans1) {
      ans3 += (n - r1);
      if (l1 + 1 == r1) {
        if (r1 < n - 1) {
          ans1 -= val[r1];
          ans1 += get(lower_bound(v.begin(), v.end(), a[r1]) - v.begin() + 1,
                      v.size());
          change(lower_bound(v.begin(), v.end(), a[r1]) - v.begin(), 1);
          r1++;
        }
        l1++;
        ans1 += val[l1];
        ans1 -= get(0, lower_bound(v.begin(), v.end(), a[l1]) - v.begin());
        change(lower_bound(v.begin(), v.end(), a[l1]) - v.begin(), -1);
      } else {
        l1++;
        ans1 += val[l1];
        ans1 -= get(0, lower_bound(v.begin(), v.end(), a[l1]) - v.begin());
        change(lower_bound(v.begin(), v.end(), a[l1]) - v.begin(), -1);
      }
    } else {
      if (r1 == n - 1) {
        l1++;
        ans1 += val[l1];
        ans1 -= get(0, lower_bound(v.begin(), v.end(), a[l1]) - v.begin());
        change(lower_bound(v.begin(), v.end(), a[l1]) - v.begin(), -1);
      } else {
        ans1 -= val[r1];
        ans1 += get(lower_bound(v.begin(), v.end(), a[r1]) - v.begin() + 1,
                    v.size());
        change(lower_bound(v.begin(), v.end(), a[r1]) - v.begin(), 1);
        r1++;
      }
    }
  }
  cout << ans3;
  return 0;
}
