401940: GYM100589 H Count Subarrays

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Count Subarraystime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Given an array of N integers A1, A2 ... AN 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 Ai, Ai + 1,..., Aj is defined as number of pairs (a, b) such that ia < bj and Aa > Ab.

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 ≤ 105
  • 0 ≤ Ai ≤ 109
  • 0 ≤ K ≤ N * (N - 1) / 2
ExamplesInput
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 Ai, Ai + 1 ... Aj.

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

Example 2. All subarrays are valid.

加入题单

上一题 下一题 算法标签: