H. Count Subarrays
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard 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 i ≤ a < b ≤ j 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
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 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.