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 long long MOD = 1e9 + 7;
const int MAX_N = 1e6;
int read() {
  int x = 0;
  char c = getchar();
  while (c < 48 || c > 57) c = getchar();
  while (c > 47 && c < 58) x *= 10, x += c - 48, c = getchar();
  return x;
}
long long readLL() {
  long long x = 0;
  char c = getchar();
  while (c < 48 || c > 57) c = getchar();
  while (c > 47 && c < 58) x *= 10LL, x += c - 48, c = getchar();
  return x;
}
void print(long long x) { printf("%I64d\n", x); }
struct T {
  int x;
  T() { x = 0; }
  T(int _x) { x = _x; }
};
T operator+(const T &L, const T &R) { return T(L.x + R.x); }
struct SegmentTree {
  vector<T> v;
  int N;
  void sz(int x) {
    N = 1;
    while (N < x) N <<= 1;
    v.assign(N << 1, T());
  }
  void add(int pos, T x) { v[N + pos] = x; }
  void build() {
    for (int i = N - 1; i > 0; i--) v[i] = v[i << 1] + v[i << 1 | 1];
  }
  T query(int l, int r) {
    T ans1 = T(), ans2 = T();
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans1 = ans1 + v[l++];
      if (r & 1) ans2 = v[--r] + ans2;
    }
    return ans1 + ans2;
  }
  void update(int pos, T x) {
    for (v[pos + N] = v[pos + N] + x, pos = (pos + N) >> 1; pos > 0; pos >>= 1)
      v[pos] = v[pos << 1] + v[pos << 1 | 1];
  }
};
int v[100002];
void reformed(int n) {
  map<long long, int> M;
  int k = 0;
  vector<int> aux(n);
  for (int i = 0; i < n; i++) aux[i] = v[i];
  sort(aux.begin(), aux.end());
  for (int i = 0; i < n; i++)
    if (M.find(aux[i]) == M.end()) M[aux[i]] = k++;
  for (int i = 0; i < n; i++) v[i] = M[v[i]];
}
int main() {
  int n = read();
  long long k = readLL();
  for (int i = 0; i < n; i++) {
    v[i] = read();
  }
  reformed(n);
  SegmentTree R, L;
  R.sz(100002);
  L.sz(100002);
  long long inv = 0, ans = 0;
  for (int i = 1; i < n; i++) {
    inv += R.query(v[i] + 1, 100001).x;
    R.update(v[i], T(1));
  }
  int r = 1;
  for (int l = 0; l < n; l++) {
    inv += R.query(0, v[l]).x + L.query(v[l] + 1, 100001).x;
    L.update(v[l], T(1));
    while (r < n && (r <= l || inv > k)) {
      inv -= L.query(v[r] + 1, 100001).x + R.query(0, v[r]).x;
      R.update(v[r], T(-1));
      r++;
    }
    if (inv <= k) ans += n - max(r, l + 1);
  }
  print(ans);
}
