2015 CodeCraft IIIT Hyderabad Replay |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

The problem statement has recently been changed. View the changes.

×
H. Count Subarrays

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputGiven an array of *N* integers *A*_{1}, *A*_{2} ... *A*_{N} and an integer *K*, count number of subarrays of *A* such that number of inversions in those subarrays is at least *K*.

Inversions in a subarray *A*_{i}, *A*_{i + 1},..., *A*_{j} is defined as number of pairs (*a*, *b*) such that *i* ≤ *a* < *b* ≤ *j* and *A*_{a} > *A*_{b}.

Input

First line consists of *N* and *K* in single line. Next line contains *N* space separated integers denoting array *A*.

Output

Print the required answer in one line.

Constraints

- 1 ≤
*N*≤ 10^{5} - 0 ≤
*A*_{i}≤ 10^{9} - 0 ≤
*K*≤*N** (*N*- 1) / 2

Examples

Input

4 1

1 2 4 0

Output

3

Input

2 0

1 2

Output

3

Note

Let’s denote by *A*[*i*, *j*] the subarray *A*_{i}, *A*_{i + 1} ... *A*_{j}.

Example 1. *A*[1, 4], *A*[2, 4], *A*[3, 4] have at least 1 inversion.

Example 2. All subarrays are valid.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 01:58:55 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|