시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB2310969.231%

문제

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

Всего Бенуа Бланк собрал $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$ --- номера улик, на которых остановится детектив в каждом из экспериментов.

예제 입력 1

6
3 3 3 4 4 5
4 2
3 4 5 6

예제 출력 1

1 1 2 2

예제 입력 2

7
1 5 7 2 10 10 6
7 0
1 2 3 4 5 6 7

예제 출력 2

1 1 1 4 4 6 7

채점 및 기타 정보

  • 예제는 채점하지 않는다.