Вера очень много работала в этом году, подавая своим коллегам пример настоящего труженика. На восьмое марта за прекрасное исполнение служебных обязанностей Вера получила подарок — долгожданный отпуск в Теплой Стране! Тяжелые трудовые будни закончились, и Вера уже нежится на пляже на берегу Теплого Моря.
Любимое хобби Веры — пляжный волейбол, и как же Вера ждала момента, когда она сможет испытать невероятный азарт этой игры! Вера уже познакомилась с несколькими симпатичными волейболистами, но она пока не решила, какая же команда достойна иметь в своем составе такого замечательного игрока.
Каждый из N капитанов команд мечтает заполучить Веру в состав своей команды, поэтому они хотят максимально проявить себя. Так как поиграть хотят все, они решили действовать следующим образом: все N команд выстроились в очередь. Первый матч иг- рается между двумя командами, которые стоят в очереди раньше остальных. Победитель игры остается на площадке, а проигравший отправляется в конец очереди. В каждом из следующих матчей победитель предыдущего играет с первой командой из очереди, а про- игравший в очередной встрече опять становится в конец очереди. Каждая команда имеет некоторую силу, причем для простоты будем предполагать, что силы всех команд различ- ны, а победителем в матче является команда, сила которой больше. Матчей может быть как угодно много.
Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствую- щем считалке номером K. Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны Q считалок, соответствующих различным значениям K. Для каждого из этих чисел K
i необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две коман- ды будут играть в матче с номером K
i.
Формат входного файла
Первая строка входных данных содержит единственное целое число N — количество команд (2 <= N <= 100 000). Вторая строка содержит N различных чисел от 1 до N — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди. Третья строка содержит единственное целое число Q (1 <= Q <= 100 000) — коли- чество известных Вере считалок. Каждая из следующих Q строк содержит число Ki (1 <= K
i <= 10
18) — номер очередного интересующего Веру матча. Обратите внимание, Ki может быть больше N. Формат выходного файла Выведите Q строк: для каждого интересующего Веру числа K
i два числа в любом порядке — силы команд, сыграющих на K
i-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.
Примеры
| Ввод |
Вывод |
4
1 3 2 4
1
3 |
3 4 |
4
2 1 4 3
3
1
5
2 |
2 1
4 2
2 4 |
Комментарии
Разберем первый тест из условия:
| |
Кто играет |
Состояние очереди |
Победитель |
Проигравший |
Матч № 1
Матч № 2
Матч № 3 |
1 3
3 2
3 4 |
2 4
4 1
1 2 |
3
3
4 |
1
2
3 |
Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.