시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB34814112043.165%

문제

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

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

입력

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

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

출력

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

예제 입력 1

4 4
1 3 7 1

예제 출력 1

3

각각 높이가 매초 $1,3,7,1$만큼 상승하는 등불을 골랐다고 하자. 처음 등불들의 높이는 $0,0,0,0$이다.

  • $1$초 후의 높이는 $1,0,0,0$이다.
  • $2$초 후의 높이는 $2,3,0,0$이다. 이때, 2번 등불이 1번 등불을 앞지른다.
  • $3$초 후의 높이는 $3,6,7,0$이다. 이때, 3번 등불이 1번 등불과 2번 등불을 앞지른다.
  • $4$초 후의 높이는 $4,9,14,1$이다.

더 이상 하나의 등불이 다른 등불을 앞지르는 경우는 없기에 사람들은 각각 $2$초에서 $1$번, $3$초에서 $2$번 총 $3$번 소원을 빈다.

예제 입력 2

5 3
10 17 19 7 10

예제 출력 2

3

예제 입력 3

10 10
1 2 3 4 5 6 7 8 9 10

예제 출력 3

45

예제 입력 4

10 9
1 2 3 4 5 6 7 8 9 10

예제 출력 4

36