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 $*a*_{*i*}$.

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* = *a*_{1}*a*_{2}... *a*_{*l*}*a*_{*r*}*a*_{*r* + 1}... *a*_{*n*}$ 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 $*b*_{*i*} > *b*_{*j*}$, where $|*b*|$ is the length of sequence $*b*$, and $*b*_{*j*}$ 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* ≤ 10^{5}, 0 ≤ *k* ≤ 10^{18})$ — the size of array $*a*$ and the maximum allowed number of inversions respectively. The next line contains $*n*$ positive integers, separated by single spaces, $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(1 ≤ *a*_{*i*} ≤ 10^{9})$ — 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.