Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P153PROJ - ROUND 3J - Số cặp nghịch thế

Cho một dãy số gồm n phần tử a[1], a[2], ..., a[n] và số nguyên k. Nhiệm vụ của bạn là hãy đếm số lượng dãy con liên tiếp thỏa mãn số cặp nghịch thế trong dãy con đó >= k.

Số cặp nghịch thế của dãy con a[i], a[i+1], ..., a[j] là số cặp (u, v) thỏa mãn i <= u < v <= j và a[u] > a[v].

Input

Dòng đầu tiên là số nguyên dương n, số lượng phần tử của dãy và số nguyên k.

Dòng tiếp theo gồm n số nguyên dương, biểu diễn a[1], a[2], ..., a[n].

Giới hạn: n <= 10^5, k <= n*(n-1)/2, 0 <= a[i] <= 10^9.

Output

In ra một số nguyên duy nhất là đáp số của bài toán.

Example

Test 1:

Input:

4 1

1 2 4 0

Output:

3

Giải thích test 1:

Các dãy con a[1->4], a[2->4], a[3->4] có một cặp nghịch thế.

 

Test 2:

Input:

2 0

1 2

Output:

3

 

 


Được gửi lên bởi:Admin
Ngày:2015-03-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.