A Subarray Problem 2

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You are given an array a of length N. You want to count the number of subarrays of length K whose sum is strictly larger than the sum of any subarray of length K-1.

Input Specification

The first line will contain the integers N, K (2 \le K \le N \le 10^5).

The second line will contain N integers, a_i (|a_i| \le 10^4).

Output Specification

Output the number of subarrays of length K whose sum is strictly larger than the sum of any subarray of length K-1.

Subtasks

Subtask 1 [30%]

N \le 10^3

Subtask 2 [70%]

No further constraints.

Sample Input

4 2
2 3 2 4

Sample Output

3

Comments

There are no comments at the moment.