CF220E.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.

小象有一个由 $n$ 个正整数组成的数组 $a$，下标从 $1$ 到 $n$。我们用 $a_i$ 表示下标为 $i$ 的数。

小象希望统计满足如下条件的整数对 $(l, r)$ 的个数：$1 \leq l < r \leq n$，且序列 $b = a_1 a_2 \dots a_l a_r a_{r+1} \dots a_n$ 中的逆序对数目不超过 $k$。

序列 $b$ 中的一个逆序对，是指在对 $b$ 进行稳定排序后相对顺序发生改变的一对元素。换言之，一个逆序对是一对整数 $(i, j)$，满足 $1 \leq i < j \leq |b|$ 且 $b_i > b_j$，其中 $|b|$ 表示序列 $b$ 的长度，$b_j$ 是其第 $j$ 个元素。

请帮助小象计算满足上述条件的整数对的个数。

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, _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 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.

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$0 \leq k \leq 10^{18}$），分别表示数组 $a$ 的大小以及允许的最大逆序对数量。
接下来一行包含 $n$ 个正整数，以单个空格分隔：$a_1,\ a_2,\ \dots,\ a_n$（$1 \leq a_i \leq 10^9$）—— 数组 $a$ 的元素。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。

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

在一行中输出一个数字——即该问题的答案。