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;
long long getint() {
  long long res = 0;
  while (1) {
    char ch = getchar();
    if (ch < '0' || ch > '9') break;
    res = res * 10 + ch - 48;
  }
  return res;
}
struct splaytree {
  struct node {
    node *left, *right, *parent;
    int size, dt, count;
    node(int _dt, node *_parent) {
      left = right = NULL;
      parent = _parent;
      size = 1;
      count = 1;
      dt = _dt;
    }
  };
  node *root;
  splaytree() { root = NULL; }
  void update(node *x) {
    x->size = (x->left ? x->left->size : 0) + (x->right ? x->right->size : 0) +
              x->count;
  }
  void tl(node *x) {
    node *y = x->parent;
    x->parent = y->parent;
    if (y->parent)
      if (y == y->parent->left)
        y->parent->left = x;
      else
        y->parent->right = x;
    y->right = x->left;
    if (x->left) x->left->parent = y;
    x->left = y;
    y->parent = x;
    update(y);
  }
  void tr(node *x) {
    node *y = x->parent;
    x->parent = y->parent;
    if (y->parent)
      if (y == y->parent->left)
        y->parent->left = x;
      else
        y->parent->right = x;
    y->left = x->right;
    if (x->right) x->right->parent = y;
    x->right = y;
    y->parent = x;
    update(y);
  }
  void splay(node *x, node *y) {
    while (x->parent != y)
      if (x->parent->parent == y)
        if (x == x->parent->left)
          tr(x);
        else
          tl(x);
      else if (x->parent == x->parent->parent->left)
        if (x == x->parent->left)
          tr(x->parent), tr(x);
        else
          tl(x), tr(x);
      else if (x == x->parent->right)
        tl(x->parent), tl(x);
      else
        tr(x), tl(x);
    update(x);
    if (!y) root = x;
  }
  void insert(int dt) {
    if (!root) {
      root = new node(dt, NULL);
      return;
    }
    node *cur = root;
    while (1)
      if (dt == cur->dt) {
        cur->count++;
        break;
      } else if (dt > cur->dt)
        if (cur->right)
          cur = cur->right;
        else {
          cur->right = new node(dt, cur);
          cur = cur->right;
          break;
        }
      else if (cur->left)
        cur = cur->left;
      else {
        cur->left = new node(dt, cur);
        cur = cur->left;
        break;
      }
    node *temp = cur;
    while (cur) update(cur), cur = cur->parent;
    splay(temp, NULL);
  }
  node *find(int dt) {
    node *cur = root;
    while (cur)
      if (dt == cur->dt) {
        splay(cur, NULL);
        return cur;
      } else if (dt > cur->dt)
        cur = cur->right;
      else
        cur = cur->left;
  }
  void remove(int dt) {
    node *p = find(dt);
    if (p->count > 1) {
      p->count--;
      update(root);
      return;
    }
    if (!p->left && !p->right) {
      root = NULL;
      return;
    } else if (!p->left) {
      node *succ = p->right;
      while (succ->left) succ = succ->left;
      splay(succ, NULL);
      root->left = NULL;
      update(root);
    } else if (!p->right) {
      node *prev = p->left;
      while (prev->right) prev = prev->right;
      splay(prev, NULL);
      root->right = NULL;
      update(root);
    } else {
      node *prev = p->left;
      while (prev->right) prev = prev->right;
      node *succ = p->right;
      while (succ->left) succ = succ->left;
      splay(prev, NULL);
      splay(succ, prev);
      root->right->left = NULL;
      update(root->right);
      update(root);
    }
  }
};
splaytree t1, t2;
int d[100010];
void lemon() {
  int n = getint();
  long long kallow = getint();
  for (int i = 1; i <= n; i++) d[i] = getint();
  int left = 0;
  long long count = 0, final = 0;
  for (int i = 1; i <= n; i++) {
    t2.insert(d[i]);
    count += (t2.root->right ? t2.root->right->size : 0);
  }
  for (int right = 1; right <= n - 1; right++) {
    t2.find(d[right]);
    count -= (t2.root->left ? t2.root->left->size : 0);
    t2.remove(d[right]);
    t1.insert(d[right]);
    count -= (t1.root->right ? t1.root->right->size : 0);
    t1.remove(d[right]);
    while (left <= right && count <= kallow) {
      left++;
      t1.insert(d[left]);
      count += (t1.root->right ? t1.root->right->size : 0);
      t2.insert(d[left]);
      count += (t2.root->left ? t2.root->left->size : 0);
      t2.remove(d[left]);
    }
    if (left > 0) final += left - 1;
  }
  printf("%I64d\n", final);
}
int main() {
  lemon();
  return 0;
}
