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 N = 100005;
int n, a[N], b[N], ord[N];
long long k, sum, ans;
struct trry {
  int n, tr[N];
  inline int lowbit(const int i) { return (i & -i); }
  void clear(int i) {
    n = i;
    memset(tr, 0, sizeof(tr));
  }
  void insert(const int pos, const int delta) {
    int s = pos;
    while (s <= n) {
      tr[s] += delta;
      s += lowbit(s);
    }
  }
  int query(const int pos) {
    int s = pos, t = 0;
    while (s) {
      t += tr[s];
      s -= lowbit(s);
    }
    return t;
  }
} tr1, tr2, tr3;
bool cmp(int i, int j) { return a[i] < a[j]; }
int main() {
  scanf("%d %I64d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    ord[i] = i;
  }
  sort(ord + 1, ord + n + 1, cmp);
  b[ord[1]] = 1;
  for (int i = 2; i <= n; ++i) {
    b[ord[i]] = a[ord[i - 1]] == a[ord[i]] ? b[ord[i - 1]] : b[ord[i - 1]] + 1;
  }
  int t1 = b[ord[n]];
  tr1.clear(t1);
  tr2.clear(t1);
  for (int i = 1; i <= n; ++i) {
    sum += i - 1 - tr1.query(b[i]);
    tr1.insert(b[i], 1);
    tr2.insert(b[i], 1);
  }
  tr1.clear(t1);
  int r = 1;
  if (sum <= k) ans += n - 1;
  tr2.insert(b[1], -1);
  sum -= tr2.query(b[1] - 1);
  for (int l = 1; l <= n; ++l) {
    while (sum > k && r < n || r < l) {
      ++r;
      tr2.insert(b[r], -1);
      sum -= tr2.query(b[r] - 1) + (l - 1 - tr1.query(b[r]));
    }
    if (sum > k && r == n) break;
    if (l != 1) ans += n - r;
    sum += l - 1 - tr1.query(b[l]) + tr2.query(b[l] - 1);
    tr1.insert(b[l], 1);
  }
  printf("%I64d\n", ans);
  return 0;
}
