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;
struct node {
  int l, r;
  long long v;
  int mid() { return (l + r) >> 1; }
} t1[101100 * 4], t2[101100 * 4];
void crt(node* tree, int l, int r, int id) {
  tree[id].l = l;
  tree[id].r = r;
  tree[id].v = 0;
  if (l == r) return;
  int mid = tree[id].mid();
  crt(tree, l, mid, id * 2);
  crt(tree, mid + 1, r, id * 2 + 1);
}
void upd(node* tree, int l, int v, int id) {
  if (tree[id].l == tree[id].r) {
    tree[id].v += v;
    return;
  }
  int mid = tree[id].mid();
  if (l <= mid)
    upd(tree, l, v, id * 2);
  else
    upd(tree, l, v, id * 2 + 1);
  tree[id].v = tree[id * 2].v + tree[id * 2 + 1].v;
}
long long qu(node* tree, int l, int r, int id) {
  if (tree[id].l >= l && tree[id].r <= r) return tree[id].v;
  int mid = tree[id].mid();
  if (r <= mid)
    return qu(tree, l, r, id * 2);
  else if (l > mid)
    return qu(tree, l, r, id * 2 + 1);
  else
    return qu(tree, l, mid, id * 2) + qu(tree, mid + 1, r, id * 2 + 1);
}
int nb[101100], a[101100], tot, n;
int bin(int key) {
  int l = 0, r = tot, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (nb[mid] == key)
      return mid;
    else if (nb[mid] > key)
      r = mid;
    else
      l = mid + 1;
  }
}
long long k, cnt;
void solve() {
  int i, j;
  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    nb[i] = a[i];
  }
  nb[n] = 0;
  nb[n + 1] = 1 << 30;
  sort(nb, nb + n + 2);
  for (i = tot = 1; i < n + 2; i++)
    if (nb[i] != nb[i - 1]) nb[tot++] = nb[i];
  crt(t1, 0, tot, 1);
  crt(t2, 0, tot, 1);
  cnt = 0;
  for (i = 0; i < n; i++) {
    int tmp = bin(a[i]);
    cnt += qu(t2, tmp + 1, tot, 1);
    upd(t2, tmp, 1, 1);
  }
  int tail = 0;
  long long ans = 0;
  for (i = 0; i < n; i++) {
    int tmp = bin(a[i]);
    if (tail == i) {
      cnt -= qu(t2, 0, tmp - 1, 1);
      cnt -= qu(t1, tmp + 1, tot, 1);
      upd(t2, tmp, -1, 1);
      tail++;
    }
    cnt += qu(t1, tmp + 1, tot, 1);
    cnt += qu(t2, 0, tmp - 1, 1);
    upd(t1, tmp, 1, 1);
    while (tail < n && cnt > k) {
      int tmp = bin(a[tail]);
      cnt -= qu(t2, 0, tmp - 1, 1);
      cnt -= qu(t1, tmp + 1, tot, 1);
      upd(t2, tmp, -1, 1);
      tail++;
    }
    ans += n - tail;
  }
  printf("%I64d\n", ans);
}
int main() {
  while (scanf("%d %I64d", &n, &k) != EOF) solve();
}
