28546번 - Исследование улик 다국어

문제

Бенуа Бланк взялся за расследование загадочного преступления и теперь активно ищет улики, которые помогут ему выйти на настоящего преступника. Как любой уважающий себя детектив, Бенуа Бланк имеет собственный метод поиска истины. Как он любит повторять, его философия заключается в том, что можно просто быть пассивным наблюдателем, и жизнь сама выведет тебя к правде.

Всего Бенуа Бланк собрал $n$ улик и расположил перед собой в ряд, $i$-я улика в ряду имеет весомость, равную $a_i$. Детектив считает, что наиболее интересными могут оказаться наименее весомые улики, и разработал следующий процесс их исследования.

Сперва Бланк выбирает какую-то улику с номером $x$ и начинает перебирать улики слева от нее. Пока слева от текущей улики находится улика меньшей или равной весомости, Бенуа Бланк перемещается к ней. При этом, эксцентричному детективу быстро надоедает однообразие, поэтому он не будет делать больше $k$ перемещений между уликами с одинаковой весомостью.

Например, если весомости улик равны $\langle 3, 3, 3, 4, 4, 5 \rangle,ドル $k = 2,ドル и детектив начинает с последней улики, он совершит четыре перемещения влево, после чего остановится.

Улики требуют тщательного изучения, поэтому Бенуа Бланк повторяет процесс $m$ раз, в $i$-й раз начиная с улики с номером $x_i$. Помогите ему побыстрее определить, на какой улике он остановится в каждом из случаев.

입력

В первой строке дано целое число $n$ --- количество улик (1ドル \leqslant n \leqslant 4 \cdot 10^5$). Во второй строке через пробел перечислены $n$ целых чисел $a_i$ --- значения весомости улик в порядке их следования в ряду (1ドル \leqslant a_i \leqslant 10^9$).

В следующей строке через пробел даны два целых числа $m$ и $k$ --- количество экспериментов и максимальное число перемещений между уликами равной весомости (1ドル \leqslant m \leqslant 4 \cdot 10^5$; 0ドル \leqslant k \leqslant n$).

В последней строке через пробел перечислены $m$ целых чисел $x_i$ --- номера улик, с которых Бенуа Бланк будет начинать исследование (1ドル \leqslant x_i \leqslant n$).

출력

Выведите через пробел $m$ целых чисел от 1ドル$ до $n$ --- номера улик, на которых остановится детектив в каждом из экспериментов.

제한

힌트