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;
typedef char* cstr;
const int oo = (~0u) >> 1;
const long long int ooll = (~0ull) >> 1;
const double inf = 1e8;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <typename type>
inline bool cmax(type& a, const type& b) {
  return a < b ? a = b, true : false;
}
template <typename type>
inline bool cmin(type& a, const type& b) {
  return a > b ? a = b, true : false;
}
template <typename type>
inline type sqr(const type& first) {
  return first * first;
}
int dbcmp(const double& a, const double& b) {
  return (a > b + eps) - (a < b - eps);
}
int sgn(const double& first) { return dbcmp(first, 0); }
template <typename type>
inline void bit_inc(vector<type>& st, int first, type inc) {
  while (first < ((int)(st).size())) st[first] += inc, first |= first + 1;
}
template <typename type>
inline type bit_sum(const vector<type>& st, int first) {
  type s = 0;
  while (first >= 0) s += st[first], first = (first & (first + 1)) - 1;
  return s;
}
inline void make_set(vector<int>& set, int size) {
  set.resize(size);
  for (int i = 0; i < (size); ++i) set[i] = i;
}
inline int find_set(vector<int>& set, int first) {
  if (set[first] != first) set[first] = find_set(set, set[first]);
  return set[first];
}
inline bool union_set(vector<int>& set, int a, int b) {
  a = find_set(set, a), b = find_set(set, b);
  return a == b ? false : set[a] = b, true;
}
int main() {
  int n;
  long long int k;
  cin >> n >> k;
  vector<int> a(n);
  map<int, int> f;
  for (int i = 0; i < (n); ++i) cin >> a[i], f[a[i]];
  int s = 0;
  for (map<int, int>::iterator i = (f).begin(); i != (f).end(); ++i)
    i->second = s++;
  vector<int> lbst(s), rbst(s);
  long long int sum = 0, ans = 0;
  for (int i = (n - 1); i >= 1; --i) {
    sum += bit_sum(rbst, f[a[i]] - 1);
    bit_inc(rbst, f[a[i]], 1);
  }
  int r = 1;
  for (int l = 0; l < (n); ++l) {
    int lc = bit_sum(lbst, s - 1) - bit_sum(lbst, f[a[l]]);
    int rc = bit_sum(rbst, f[a[l]] - 1);
    bit_inc(lbst, f[a[l]], 1);
    sum += lc + rc;
    while (r <= l || (r < n && sum > k)) {
      int lc = bit_sum(lbst, s - 1) - bit_sum(lbst, f[a[r]]);
      int rc = bit_sum(rbst, f[a[r]] - 1);
      bit_inc(rbst, f[a[r]], -1);
      sum -= lc + rc;
      r++;
    }
    if (sum <= k) ans += n - r;
  }
  cout << ans << endl;
}
