Oak Tree Heights

Interview

Time limit1sMemory limit1024 MB

Summary

Given N oak heights and a neighbor distance D, find the oak whose height exceeds the average height of its neighbors by the largest margin.

Level: Medium4 of 10
Topics: Prefix sum, Array
Solved: No attempts yet

Problem

Along a highway, N oak trees grow in a row, numbered 1 to N from left to right. Two oaks are adjacent if no more than D oaks grow between them. Equivalently, two oaks are adjacent if their numbers differ by at most $D + 1$ .

Kėkštas plans to build a nest in one of these oaks. He wants to choose the oak whose height exceeds the average height of its adjacent oaks by the largest margin.

Find that oak.

Input

The first line contains two integers N and D. Each of the next N lines contains one integer $a_i$ , the height of the i-th oak ( $1 \le i \le N$ ).

Output

Print one integer, the number of the oak Kėkštas should choose. If several answers are possible, print any of them.

Constraints

$2 \le N \le 1\,000\,000$
$0 \le D \le N - 1$
$1 \le a_i \le 1\,000\,000$

Examples1

Example 1
Input
```
4 0
1
2
2
1
```
Expected output
```
3
```