Уже много лет так получалось, что день города Н проводился в самый дождливый день лета. Новый мэр хочет разрушить эту печальную традицию; для этого он собирается выбрать не очень дождливый день для праздника. Мэр знает прогноз погоды на \(n\) дней лета. В \(i\)-й день выпадет \(a_i\) миллиметров осадков. Все значения \(a_i\) различны.
Мэр знает, что горожане будут следить за погодой в течение \(x\) дней до праздника и \(y\) дней после. Поэтому он определил, что день \(d\) является не очень дождливым, если \(a_d\) меньше, чем объемы осадков в каждый из \(x\) дней до дня \(d\) и в каждый из \(y\) дней после дня \(d\). Другими словами, \(a_d < a_j\) должно выполняться для всех \(d - x \le j < d\) и \(d < j \le d + y\). Горожане следят за погодой только летом, поэтому рассматриваются только такие \(j\), что \(1 \le j \le n\).
Помогите мэру найти самый ранний не очень дождливый день лета.
Выходные данные
Выведите одно целое число — номер самого раннего не очень дождливого дня лета. Можно показать, что ответ всегда существует.
Примечание
В первом примере дни \(3\) и \(8\) не очень дождливые. День \(3\) более ранний.
Во втором примере \(3\) не является не очень дождливым днем, потому что \(3 + y = 6\), но \(a_3 > a_6\). Поэтому ответ — день \(8\). Обратите внимание, что \(8 + y = 11\), но мы не рассматриваем день \(11\), так как это уже не лето.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2 2
10 9 6 7 8 3 2 1 4 5
|
3
|
|
2
|
10 2 3
10 9 6 7 8 3 2 1 4 5
|
8
|
|
3
|
5 5 5
100000 10000 1000 100 10
|
5
|