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 INF = (int)1E9;
const double INFD = 1E9;
const long long INFLL = (long long)1E15;
const long long MOD = (long long)1E9 + 7;
const long double PI = acos(-1);
const long double EPS = 1E-9;
bool between(int x, int l, int r) { return (l <= x && x <= r); }
string tostring(int x) {
  char dum[20];
  sprintf(dum, "%d", x);
  string ret(dum);
  return ret;
}
inline void work(int kasus) {}
pair<int, int> A[100010], B[100010];
vector<pair<int, int> > tree[4 * 100010];
long long inv = 0;
int n;
long long m;
vector<pair<int, int> > temp;
void Merge(int cur, int l, int mid, int r) {
  int idx1 = l, idx2 = mid + 1;
  temp.clear();
  while (idx1 <= mid || idx2 <= r) {
    if (idx1 > mid) {
      temp.push_back(A[idx2++]);
      continue;
    }
    if (idx2 > r) {
      temp.push_back(A[idx1++]);
      continue;
    }
    if (A[idx1].first > A[idx2].first) {
      inv += (long long)(mid - idx1 + 1);
      temp.push_back(A[idx2++]);
    } else
      temp.push_back(A[idx1++]);
  }
  int idx = l;
  for (auto data : temp) A[idx++] = data;
  tree[cur] = temp;
}
void Msort(int cur, int l, int r) {
  if (l == r) {
    tree[cur].push_back(A[l]);
    return;
  }
  int mid = (l + r) / 2;
  Msort(cur * 2 + 1, l, mid);
  Msort(cur * 2 + 2, mid + 1, r);
  Merge(cur, l, mid, r);
}
inline void DebugTree() {
  for (int i = 0; i < 4 * n; i += 1) {
    if (tree[i].empty()) continue;
    cout << i << " : ";
    for (auto data : tree[i]) cout << data.first << "," << data.second << " ";
    cout << endl;
  }
}
inline int getInv(int tipe, int cur, int x) {
  if (tree[cur].empty()) return 0;
  int l = 0, r = tree[cur].size() - 1, ret = INF, mid;
  if (tipe == 1) ret = -ret;
  while (l <= r) {
    mid = (l + r) / 2;
    if (tipe == 0) {
      if (tree[cur][mid].first > x)
        ret = min(ret, mid), r = mid - 1;
      else
        l = mid + 1;
    } else {
      if (tree[cur][mid].first < x)
        ret = max(ret, mid), l = mid + 1;
      else
        r = mid - 1;
    }
  }
  if (ret > 1E6 || ret < -1E6) return 0;
  if (tipe == 0) return (int)tree[cur].size() - ret;
  return ret + 1;
}
int query(int tipe, int ql, int qr, int x, int cur = 0, int l = 0,
          int r = n - 1) {
  if (l > r || r < ql || l > qr) return 0;
  if (ql <= l && r <= qr) return getInv(tipe, cur, x);
  int mid = (l + r) / 2;
  return query(tipe, ql, qr, x, cur * 2 + 1, l, mid) +
         query(tipe, ql, qr, x, cur * 2 + 2, mid + 1, r);
}
int main() {
  scanf("%d%I64d", &n, &m);
  for (int i = 0; i < n; i += 1)
    scanf("%d", &A[i].first), A[i].second = i, B[i] = A[i];
  Msort(0, 0, n - 1);
  for (int i = 0; i < n; i += 1) A[i] = B[i];
  long long ans = 0;
  long long ori = inv;
  int start = 1;
  for (int i = 0; i < n; i += 1) {
    if (start <= i + 1) start = i + 1, inv = ori;
    while (start < n) {
      if (inv <= m) {
        ans += (long long)(n - start);
        break;
      } else {
        inv -= ((long long)query(0, 0, i, A[start].first) +
                (long long)query(1, start + 1, n - 1, A[start].first));
        start++;
      }
    }
    if (i + 1 < n)
      inv += ((long long)query(0, 0, i, A[i + 1].first) +
              (long long)query(1, start, n - 1, A[i + 1].first));
  }
  printf("%I64d\n", ans);
  return 0;
}
