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>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
int arr[100005];
typedef struct tree* PTree;
struct tree {
  tree() {
    val = 0;
    l = r = NULL;
  };
  long long val;
  PTree l, r;
};
PTree build(int l, int r) {
  if (l == r) {
    PTree a = new tree();
    a->val = arr[l];
    return a;
  }
  PTree root = new tree();
  int m = (l + r) >> 1;
  root->l = build(l, m);
  root->r = build(m + 1, r);
  root->val = root->l->val + root->r->val;
  return root;
}
PTree lr[100005], rr[100005];
long long find(PTree root, int l, int r, int L, int R) {
  if (R < L) return 0;
  if (l == L && r == R) return root->val;
  long long res = 0;
  int m = (l + r) >> 1;
  if (R <= m) return res + find(root->l, l, m, L, R);
  if (L > m) return res + find(root->r, m + 1, r, L, R);
  return res + find(root->l, l, m, L, m) + find(root->r, m + 1, r, m + 1, R);
}
PTree update(PTree root, int l, int r, int pos, int add) {
  if (l == r) {
    PTree a = new tree();
    a->val = root->val + add;
    return a;
  }
  PTree a = new tree();
  a->l = root->l;
  a->r = root->r;
  int m = (l + r) >> 1;
  if (pos <= m) {
    a->l = update(root->l, l, m, pos, add), a->r = root->r;
  } else if (pos > m) {
    a->l = root->l, a->r = update(root->r, m + 1, r, pos, add);
  }
  a->val = 0;
  if (a->l) a->val += a->l->val;
  if (a->r) a->val += a->r->val;
  return a;
}
vector<int> v;
int a[100005];
int fen[4][100005];
void upd(int i, int pos, int n, int add) {
  for (; pos < n; pos |= (pos + 1)) fen[i][pos] += add;
}
long long fnd(int i, int pos) {
  long long ret = 0;
  for (; pos >= 0; pos = (pos & (pos + 1)) - 1) ret += fen[i][pos];
  return ret;
}
int main() {
  int n;
  long long k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    v.push_back(a[i]);
  }
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 0; i < n; ++i)
    a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
  PTree cur = build(0, n - 1);
  lr[0] = update(cur, 0, n - 1, a[0], 1);
  for (int i = 1; i < n; ++i) lr[i] = update(lr[i - 1], 0, n - 1, a[i], 1);
  rr[n - 1] = update(cur, 0, n - 1, a[n - 1], 1);
  for (int i = n - 2; i >= 0; --i) rr[i] = update(rr[i + 1], 0, n - 1, a[i], 1);
  upd(0, n - 1 - a[0], n, 1);
  int l = 1, r = 1;
  long long inv = 0, ci = (a[0] > a[1]) +
                          (n > 2 ? find(rr[2], 0, n - 1, 0, a[1] - 1) : 0);
  PTree tmp = cur;
  for (int i = 0; i < n; ++i) {
    inv += find(tmp, 0, n - 1, a[i] + 1, n - 1);
    tmp = update(tmp, 0, n - 1, a[i], 1);
  }
  if (inv <= k) {
    cout << 1LL * n * (n - 1) / 2 << endl;
    return 0;
  }
  long long mn = inv - k, ans = 0;
  int cr = 2;
  upd(1, n - 1 - a[0], n, 1);
  upd(1, n - 1 - a[1], n, 1);
  cur = update(cur, 0, n - 1, a[1], 1);
  for (int i = 1; i < n; ++i) {
    while (cr < n - 1 && ci < mn) {
      ci += find(rr[cr + 1], 0, n - 1, 0, a[cr] - 1);
      ci += fnd(1, n - 1 - a[cr] - 1);
      ci -= find(cur, 0, n - 1, a[cr] + 1, n - 1);
      cur = update(cur, 0, n - 1, a[cr], 1);
      upd(1, n - 1 - a[cr], n, 1);
      ++cr;
    }
    if (ci >= mn) ans += (n - 1) - cr + 1;
    ci -= fnd(0, n - 1 - a[i] - 1);
    ci -= find(rr[cr], 0, n - 1, 0, a[i] - 1);
    upd(0, n - 1 - a[i], n, 1);
    cur = update(cur, 0, n - 1, a[i], -1);
  }
  cout << ans << endl;
  return 0;
}
