This problem is the hard version of the Aslı, Deren and Rainy Days (Easy) problem. In the hard version of the problem, the numbers \(\mathbf{a}\) and \(\mathbf{b}\) can be up to \(\mathbf{N}\).

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 \mathbf{N}\)
• \(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.