## Aslı, Deren and Rainy Days (Easy)

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Deren and Aslı are best friends and have missed each other a lot. They now have an opportunity to see each other. They can meet up once in the upcoming $$\mathbf{N}$$ day period. However, it is going to rain each of these days. So they want to meet up on a day where it does not rain too much. They also want to see each other as soon as possible. So, they have come up with a solution. They say that the $$i$$th day is optimal if, on day number $$i$$, it rains less than the previous $$\mathbf{a}$$ days and the next $$\mathbf{b}$$ days. Can you find the earliest optimal day so that Aslı and Deren can see each other and be happy?

The days are numbered from 1 to $$\mathbf{N}$$. They are available only on those $$\mathbf{N}$$ days, so they don't take any other day into account. It is guaranteed that there exists a solution.

#### Input:

The first line contains three integers, $$\mathbf{N}$$, $$\mathbf{a}$$, and $$\mathbf{b}$$. The second line will contain $$\mathbf{N}$$ distinct integers $$r_1, r_2, ..., r_n$$ where $$r_i$$ represents the amount of rain on the $$i$$th day.

• $$1 \leq \mathbf{N} \leq 10^5$$
• $$0 \leq \mathbf{a}, \mathbf{b} \leq 7$$
• $$1 \leq r_i \leq 10^9$$

#### Output:

Print a single integer, the index of the earliest optimal day.

#### Examples:

Input:

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

Output:

3

Input:

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

Output:

8

Input:

6 6 6
6 5 4 3 2 1

Output:

6
##### Explanations:

In the first test case, the 3rd day is valid (where it rains 5 units). Because there aren't any less-rainy-days in the previous 2 days or in the next 2 days. In the second test case, the 8th day is valid (where it rains 1 unit). Because there aren't any less-rainy-days in the previous 2 days or in the next 3 days (The days after the $$\mathbf{N}$$th day are out of their scope so they are not taken into consideration.). And in the third test case, the 6th day is valid (where it rains 1 unit). Because there aren't any less-rainy-days in the previous 6 days or in the following 6 days.