A8755 | Little Elephant and Inversions

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.

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.

In a single line print a single number — the answer to the problem.