Float Lanterns

Time limit1sMemory limit1024 MB

Summary

Pick S consecutive lanterns and count pairs where a later-released lantern rises faster than an earlier one; output the maximum count over all windows.

Level: Hard8 of 10
Topics: Sliding window, Divide and conquer, Array
Solved: No attempts yet

Problem

Geonguseu prepared $N$ lanterns that rise without limit into the sky to close out the festival. The lanterns are numbered $1$ to $N$ from left to right, and lantern $i$ rises by $A_i$ every second. At the start, all lanterns are placed at height $0$ . When the festival ends, Geonguseu will pick $S$ consecutive lanterns and release them one second apart, in order of increasing number.

When one lantern overtakes other lanterns, people make one wish for each lantern it overtakes. Geonguseu wants to choose the lanterns to release so that people make as many wishes as possible. Among all ways to pick $S$ consecutive lanterns, what is the maximum number of wishes people can make?

Input

The first line contains the number of lanterns $N$ and the number of lanterns to release $S$ , separated by a space. $\left( 2 \leq N \leq 100000;\ 1 \leq S \leq N \right)$

The second line contains $N$ integers $A_i$ , separated by spaces, where $A_i$ is how much lantern $i$ rises each second. $\left( 1 \leq A_i \leq 10^{9} \right)$

Output

Print the number of wishes people make when Geonguseu chooses the lanterns to release so that this number is as large as possible.

Examples4

Example 1
Input
```
4 4
1 3 7 1
```
Expected output
```
3
```
Example 2
Input
```
5 3
10 17 19 7 10
```
Expected output
```
3
```
Example 3
Input
```
10 10
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
45
```
Example 4
Input
```
10 9
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
36
```