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 double tiaohe = 0.57721566490153286060651209;
long long oula(long long x) {
  long long res = x;
  for (register int i = 2; i <= x / i; ++i) {
    if (x % i == 0) {
      res = res / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) res = res / x * (x - 1);
  return res;
}
long long quickmod(long long a, long long n, long long m) {
  long long s = 1;
  while (n) {
    if (n & 1) {
      s = s * a % m;
    }
    a = (a * a) % m;
    n = n / 2;
  }
  return s;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
void ex_gcd(long long a, long long b, long long &x, long long &y,
            long long &d) {
  if (!b) {
    d = a, x = 1, y = 0;
  } else {
    ex_gcd(b, a % b, y, x, d);
    y -= x * (a / b);
  }
}
long long inv(long long t, long long p) {
  long long d, x, y;
  ex_gcd(t, p, x, y, d);
  return d == 1 ? (x % p + p) % p : -1;
}
bool isPrime(long long x) {
  if (x == 2) return true;
  if (x % 2 == 0) return false;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
double eqa = (1 + sqrt(5.0)) / 2.0;
const int N = 6e5 + 5;
int t;
long long k;
int n, tree[N], tree2[N], tree3[N];
void add(int k, int num) {
  for (int i = k; i <= n; i += i & -i) tree[i] += num;
}
void add2(int k, int num) {
  for (int i = k; i <= n; i += i & -i) tree2[i] += num;
}
void add3(int k, int num) {
  for (int i = k; i <= n; i += i & -i) tree3[i] += num;
}
int read(int k) {
  int sum = 0;
  for (int i = k; i > 0; i -= i & -i) sum += tree[i];
  return sum;
}
int read2(int k) {
  int sum = 0;
  for (int i = k; i > 0; i -= i & -i) sum += tree2[i];
  return sum;
}
int read3(int k) {
  int sum = 0;
  for (int i = k; i > 0; i -= i & -i) sum += tree3[i];
  return sum;
}
int a[N], b[N], g[N], g2[N];
int main() {
  cin >> n >> k;
  long long sum = 0;
  for (register int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  sort(a + 1, a + n + 1);
  int len = unique(a + 1, a + n + 1) - a - 1;
  for (register int i = 1; i <= n; ++i)
    b[i] = lower_bound(a + 1, a + 1 + len, b[i]) - a;
  for (register int i = 1; i <= n; ++i) {
    g2[i] = read2(n) - read2(b[i]);
    add2(b[i], 1);
  }
  for (register int i = n; i >= 1; --i) {
    g[i] = read(b[i] - 1);
    sum += g[i];
    g[i] += g2[i];
    add(b[i], 1);
  }
  long long gap = sum - k;
  long long ans = 0;
  if (gap <= 0) {
    printf("%lld\n", (long long)n * (n - 1) / 2);
    return 0;
  }
  long long now = 0;
  int l = 1, r = 2;
  for (register int i = 2; i <= n - 1; ++i) {
    now += g[i];
    now -= read3(n) - read3(b[i]);
    add3(b[i], 1);
    if (now >= gap) {
      r = i;
      break;
    }
  }
  ans += n - r;
  while (l <= n - 3) {
    l++;
    now -= g[l];
    now += read3(b[l] - 1);
    add3(b[l], -1);
    while (r <= n - 2 && now < gap) {
      r++;
      now += g[r] - (read3(n) - read3(b[r]));
      add3(b[r], 1);
    }
    if (r == l) r = l + 1;
    if (now >= gap) {
      ans += n - r;
    } else
      break;
  }
  cout << ans << endl;
  return 0;
}
