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 int maxn = 100000 + 10;
int a[maxn];
int mark[maxn];
long long seg[4 * maxn], seg1[4 * maxn];
vector<int> v;
int n;
long long inv, k;
long long now, ans;
void Add(int s, int e, int tag, int pos, int val) {
  seg[tag] += val;
  if (s == e) return;
  int m = (s + e) / 2;
  if (pos > m)
    Add(m + 1, e, tag * 2 + 1, pos, val);
  else
    Add(s, m, tag * 2, pos, val);
  return;
}
long long Get(int s, int e, int tag, int l, int r) {
  if (s >= l && e <= r) return seg[tag];
  if (s > r || e < l) return 0;
  int m = (s + e) / 2;
  return Get(s, m, tag * 2, l, r) + Get(m + 1, e, tag * 2 + 1, l, r);
}
void Add1(int s, int e, int tag, int pos, int val) {
  seg1[tag] += val;
  if (s == e) return;
  int m = (s + e) / 2;
  if (pos > m)
    Add1(m + 1, e, tag * 2 + 1, pos, val);
  else
    Add1(s, m, tag * 2, pos, val);
  return;
}
long long Get1(int s, int e, int tag, int l, int r) {
  if (s >= l && e <= r) return seg1[tag];
  if (s > r || e < l) return 0;
  int m = (s + e) / 2;
  return Get1(s, m, tag * 2, l, r) + Get1(m + 1, e, tag * 2 + 1, l, r);
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    v.push_back(a[i]);
  }
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
  for (int i = 1; i <= n; i++) {
    Add(1, n, 1, a[i], 1);
    inv += Get(1, n, 1, a[i] + 1, n);
  }
  Add(1, n, 1, a[1], -1);
  now += Get(1, n, 1, 1, a[1] - 1);
  int p = 2;
  for (int i = 1; i < n; i++) {
    if (i == p) {
      now += Get(1, n, 1, 1, a[p] - 1);
      now += Get1(1, n, 1, a[p] + 1, n);
      Add(1, n, 1, a[p], -1);
      p++;
    }
    now -= Get(1, n, 1, 1, a[i] - 1);
    now -= Get1(1, n, 1, a[i] + 1, n);
    Add1(1, n, 1, a[i], 1);
    while (inv - now > k) {
      now += Get(1, n, 1, 1, a[p] - 1);
      now += Get1(1, n, 1, a[p] + 1, n);
      Add(1, n, 1, a[p], -1);
      p++;
    }
    if (p > n) break;
    ans += (n - p + 1);
  }
  cout << ans;
}
