Little Elephant and Inversions

题意翻译

## 题意翻译 给你一个长度为 n 的序列 A[1], A[2], …, A[n]. 问你有多少组 (l, r) （1 <= l < r <= n) 满足 A[1], A[2], …, A[l], A[r], A[r+1], ..., A[n] 的逆序对个数不超过 k。 ## **输入格式** 第一行两个整数 n，k (2<=n<=10^5,0<=k<=10^18)。下一行为一个长度为 n 的序列 A[1], A[2], …, A[n]。 ## 输出格式 在一行中输出问题的答案。

题目描述

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&lt;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&lt;j<=|b| $ and $ b_{i}&gt;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.

输入输出样例

输入样例 #1

3 1
1 3 2

输出样例 #1

3

输入样例 #2

5 2
1 3 2 1 7

输出样例 #2

6