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 warning(disable : 4996)
using namespace std;
namespace Xrocks {}
using namespace Xrocks;
namespace Xrocks {
class in {
} user_input;
class out {
} output;
in& operator>>(in& X, int& Y) {
  scanf("%d", &Y);
  return X;
}
in& operator>>(in& X, char* Y) {
  scanf("%s", Y);
  return X;
}
in& operator>>(in& X, float& Y) {
  scanf("%f", &Y);
  return X;
}
in& operator>>(in& X, double& Y) {
  scanf("%lf", &Y);
  return X;
}
in& operator>>(in& X, char& C) {
  scanf("%c", &C);
  return X;
}
in& operator>>(in& X, string& Y) {
  cin >> Y;
  return X;
}
in& operator>>(in& X, long long& Y) {
  scanf("%lld", &Y);
  return X;
}
template <typename T>
in& operator>>(in& X, vector<T>& Y) {
  for (auto& x : Y) user_input >> x;
  return X;
}
template <typename T>
out& operator<<(out& X, const T& Y) {
  cout << Y;
  return X;
}
template <typename T>
out& operator<<(out& X, vector<T>& Y) {
  for (auto& x : Y) output << x << " ";
  return X;
}
out& operator<<(out& X, const int& Y) {
  printf("%d", Y);
  return X;
}
out& operator<<(out& X, const char& C) {
  printf("%c", C);
  return X;
}
out& operator<<(out& X, const string& Y) {
  printf("%s", Y.c_str());
  return X;
}
out& operator<<(out& X, const long long& Y) {
  printf("%lld", Y);
  return X;
}
out& operator<<(out& X, const float& Y) {
  printf("%f", Y);
  return X;
}
out& operator<<(out& X, const double& Y) {
  printf("%lf", Y);
  return X;
}
out& operator<<(out& X, const char Y[]) {
  printf("%s", Y);
  return X;
}
template <typename T>
T max(T A) {
  return A;
}
template <typename T, typename... args>
T max(T A, T B, args... S) {
  return max(A > B ? A : B, S...);
}
template <typename T>
T min(T A) {
  return A;
}
template <typename T, typename... args>
T min(T A, T B, args... S) {
  return min(A < B ? A : B, S...);
}
template <typename T>
void vectorize(int y, vector<T>& A) {
  A.resize(y);
}
template <typename T, typename... args>
void vectorize(int y, vector<T>& A, args&&... S) {
  A.resize(y);
  vectorize(y, S...);
}
long long fast(long long a, long long b, long long pr) {
  if (b == 0) return 1 % pr;
  long long ans = 1 % pr;
  while (b) {
    if (b & 1) ans = (ans * a) % pr;
    b >>= 1;
    a = (a * a) % pr;
  }
  return ans;
}
int readInt() {
  int n = 0;
  int ch = getchar_unlocked();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar_unlocked();
  }
  while (ch >= '0' && ch <= '9')
    n = (n << 3) + (n << 1) + ch - '0', ch = getchar_unlocked();
  n = n * sign;
  return n;
}
long long readLong() {
  long long n = 0;
  int ch = getchar_unlocked();
  int sign = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') sign = -1;
    ch = getchar_unlocked();
  }
  while (ch >= '0' && ch <= '9')
    n = (n << 3) + (n << 1) + ch - '0', ch = getchar_unlocked();
  n = n * sign;
  return n;
}
long long readBin() {
  long long n = 0;
  int ch = getchar_unlocked();
  int sign = 1;
  while (ch < '0' || ch > '1') {
    if (ch == '-') sign = -1;
    ch = getchar_unlocked();
  }
  while (ch >= '0' && ch <= '1')
    n = (n << 1) + (ch - '0'), ch = getchar_unlocked();
  return n;
}
long long inv_(long long val,
               long long pr = static_cast<long long>(1000000007)) {
  return fast(val, pr - 2, pr);
}
}  // namespace Xrocks
class seg_tree {
  vector<int> tree;
  int n;
  int get_size(int a) {
    int r = 2;
    --a;
    while (a) {
      a >>= 1;
      r <<= 1;
    }
    return r;
  }

 public:
  void construct(int a) {
    tree.resize(get_size(a));
    n = a - 1;
  }
  void add(int pos, int vf) { add(pos, 0, n, 1, vf); }
  void add(int pos, int l, int r, int c, int val) {
    if (pos < l || pos > r) return;
    if (l == r) {
      tree[c] += val;
      return;
    }
    int mid = (l + r) >> 1;
    add(pos, l, mid, c << 1, val);
    add(pos, mid + 1, r, (c << 1) + 1, val);
    tree[c] = tree[c << 1] + tree[(c << 1) + 1];
  }
  int sum(int l, int r) { return sum(l, r, 0, n, 1); }
  int sum(int x, int y, int l, int r, int c) {
    if (y < l || x > r) return 0;
    if (x <= l && y >= r) return tree[c];
    return sum(x, y, l, (l + r) >> 1, c << 1) +
           sum(x, y, ((l + r) >> 1) + 1, r, (c << 1) + 1);
  }
};
class solve {
 public:
  solve() {
    int n;
    long long k;
    user_input >> n >> k;
    vector<int> v(n), idx(n), invc(n), val2(n);
    user_input >> v;
    for (auto& x : idx) x = &x - &idx[0];
    sort(idx.begin(), idx.end(),
         [&](const int& a, const int& b) { return v[a] < v[b]; });
    seg_tree S[2];
    S[0].construct(n + 2);
    S[1].construct(n + 2);
    val2[idx[0]] = 1;
    for (int i = 1; i < n; i++) {
      if (v[idx[i]] == v[idx[i - 1]]) {
        val2[idx[i]] = val2[idx[i - 1]];
      } else
        val2[idx[i]] = i + 1;
    }
    long long tot = 0;
    for (int i = n - 1; i >= 0; i--) {
      invc[i] = S[0].sum(0, val2[i] - 1);
      tot += invc[i];
      S[0].add(val2[i], 1);
    }
    int j = 1;
    S[1].add(val2[0], 1);
    S[0].add(val2[0], -1);
    long long ans = 0;
    for (int i = 0; i + 1 < n; i++) {
      while ((j + 1 < n && tot > k) || j == i) {
        tot -= invc[j] + S[1].sum(val2[j] + 1, n + 1);
        S[0].add(val2[j], -1);
        ++j;
      }
      if (tot <= k) {
        ans += n - j;
      }
      tot += S[1].sum(val2[i + 1] + 1, n + 1) + S[0].sum(0, val2[i + 1] - 1);
      S[1].add(val2[i + 1], 1);
    }
    output << ans;
  }
};
int32_t main() {
  int t = 1, i = 1;
  if (0 || 0) scanf("%d", &t);
  while (t--) {
    if (0) printf("Case #%d: ", i++);
    new solve;
  }
  output << "\n";
  return 0;
}
