Исследование улик
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
113$$$n, m \leqslant 10$$$полная
212$$$n, m \leqslant 1000$$$, $$$k = 0$$$полная
315$$$n, m \leqslant 1000$$$, $$$k = 1$$$полная
418$$$n, m \leqslant 1000$$$1 – 3первая ошибка
519$$$k = 0$$$2первая ошибка
623нет1 – 5первая ошибка

Примеры

Входные данные
6
3 3 3 4 4 5
4 2
3 4 5 6
Выходные данные
1 1 2 2 
Входные данные
7
1 5 7 2 10 10 6
7 0
1 2 3 4 5 6 7
Выходные данные
1 1 1 4 4 6 7