Codeforces Round 576 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

implementation

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. City Day

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFor years, the Day of city N was held in the most rainy day of summer. New mayor decided to break this tradition and select a not-so-rainy day for the celebration. The mayor knows the weather forecast for the $$$n$$$ days of summer. On the $$$i$$$-th day, $$$a_i$$$ millimeters of rain will fall. All values $$$a_i$$$ are distinct.

The mayor knows that citizens will watch the weather $$$x$$$ days before the celebration and $$$y$$$ days after. Because of that, he says that a day $$$d$$$ is not-so-rainy if $$$a_d$$$ is smaller than rain amounts at each of $$$x$$$ days before day $$$d$$$ and and each of $$$y$$$ days after day $$$d$$$. In other words, $$$a_d < a_j$$$ should hold for all $$$d - x \le j < d$$$ and $$$d < j \le d + y$$$. Citizens only watch the weather during summer, so we only consider such $$$j$$$ that $$$1 \le j \le n$$$.

Help mayor find the earliest not-so-rainy day of summer.

Input

The first line contains three integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le x, y \le 7$$$) — the number of days in summer, the number of days citizens watch the weather before the celebration and the number of days they do that after.

The second line contains $$$n$$$ distinct integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the rain amount on the $$$i$$$-th day.

Output

Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.

Examples

Input

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

Output

3

Input

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

Output

8

Input

5 5 5 100000 10000 1000 100 10

Output

5

Note

In the first example days $$$3$$$ and $$$8$$$ are not-so-rainy. The $$$3$$$-rd day is earlier.

In the second example day $$$3$$$ is not not-so-rainy, because $$$3 + y = 6$$$ and $$$a_3 > a_6$$$. Thus, day $$$8$$$ is the answer. Note that $$$8 + y = 11$$$, but we don't consider day $$$11$$$, because it is not summer.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2023 11:24:02 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|