등불 날리기

시간 제한1초메모리 제한1024 MB

요약

연속된 S개의 등불을 골라, 나중에 띄우는 등불의 상승 속도가 먼저 띄운 등불보다 빠른 쌍의 수를 구합니다. 그 수가 최대가 되는 값을 출력합니다.

난이도: 어려움10점 중 8점
유형: 슬라이딩 윈도우, 분할 정복, 배열
정답자: 아직 제출이 없습니다

문제

건구스는 축제의 마무리를 장식하기 위해 하늘로 무한히 상승하는 $N$ 개의 등불을 준비했다. 등불은 왼쪽부터 차례대로 $1$ 번부터 번호가 매겨져 있으며, $i$ 번 등불은 매초 높이가 $A_i$ 만큼 상승한다. 처음에는 모든 등불을 높이 $0$ 에 준비해 두었다. 건구스는 축제가 끝날 때, 연속하는 $S$ 개의 등불을 골라 $1$ 초 간격으로 번호가 작은 것부터 날려 보내려고 한다.

등불 하나가 다른 등불들을 앞지르면, 사람들은 앞지르는 등불의 개수만큼 소원을 빈다. 건구스는 사람들이 최대한 많은 소원을 빌도록 날려 보낼 등불을 고르려고 한다. 연속하는 $S$ 개의 등불을 적절히 골라 날려 보냈을 때, 사람들은 최대 몇 개의 소원을 빌 수 있을까?

입력

첫째 줄에 건구스가 준비한 등불의 개수 $N$ 과 날려 보낼 등불의 개수 $S$ 가 공백으로 구분되어 주어진다. $\left( 2 \leq N \leq 100000;\ 1 \leq S \leq N \right)$

둘째 줄에 각 등불이 매초 상승하는 정도를 나타내는 $N$ 개의 정수 $A_i$ 가 순서대로 공백으로 구분되어 주어진다. $\left( 1 \leq A_i \leq 10^{9} \right)$

출력

사람들이 최대한 많은 소원을 빌도록 날려 보낼 등불들을 골랐을 때, 소원을 비는 횟수를 출력한다.

예제4

예제 1
입력
```
4 4
1 3 7 1
```
예상 출력
```
3
```
예제 2
입력
```
5 3
10 17 19 7 10
```
예상 출력
```
3
```
예제 3
입력
```
10 10
1 2 3 4 5 6 7 8 9 10
```
예상 출력
```
45
```
예제 4
입력
```
10 9
1 2 3 4 5 6 7 8 9 10
```
예상 출력
```
36
```