Вася только устроился в компанию, но уже успел полюбить столовую в офисе. Теперь он каждый день ходит в эту столовую, где на выбор предлагается 𝑛 различных блюд. Известно, что 𝑖-е блюдо стоит 𝑥𝑖 рублей. Вася планирует в ближайшие 𝑞 дней покупать по одному блюду в день. Он решил, что в 𝑖-ый день он не хочет тратить на еду больше, чем 𝑚𝑖 рублей. Помогите Васе узнать, насколько велик будет выбор блюд для него в каждый из дней, если компания оплатит Васе половину стоимости обеда.

Входные данные

В первой строке входных данных содержится целое число 𝑛 (1 ≤ 𝑛 ≤ 200000) — количество блюд в столовой. Во второй строке входных данных содержится 𝑛 чисел 𝑥𝑖 (1 ≤ 𝑥𝑖 ≤ 200000) — цена 𝑖-го блюда. В третьей строке входных данных содержится число 𝑞 (1 ≤ 𝑞 ≤ 200000) — количество дней, в течение которых Вася планирует ходить в столовую. В следующих 𝑞 строках входных данных содержатся целые числа 𝑚𝑖 (1 ≤ 𝑚𝑖 ≤ 200000) — количество денег, которое есть у Васи в 𝑖-й день.

Выходные данные

Выведите 𝑞 целых чисел (каждое число в новой строке), 𝑖-е из которых должно равняться количеству блюд, на которые у Васи может хватить денег в день 𝑖.

Пример

Входные данные

6 20 16 12 22

Выходные данные

Примечание

В первом запросе ни на одно блюдо Васе не хватит денег (он может купить блюдо максимальной стоимостью 2 рубля – один он оплатил бы сам, а второй компания). Во втором запросе Васе хватит денег, чтобы купить одно из четырех первых блюд. В третьем запросе Васе хватит денег только на первое блюдо. И в последнем запросе Вася может позволить себе любое блюдо.

Тип	Batch
Ограничение по времени	2 секунды
Ограничение по памяти	256 МБ
Команды компиляции	C++11 / g++	`/usr/bin/g++ -DEVAL -std=c++11 -O2 -pipe -static -s -o A A.cpp`

Задача B. Путь на работу

Добираться Васе до офиса не так уж и сложно — от метро до офиса компании курсирует шаттл. Будем считать, что он едет по прямой от метро (точка 0) до офиса (точка 𝑠) и обратно, преодолевая 1 метр за 𝑡1 секунд в обоих направлениях. То есть шаттл ходит равномерно прямолинейно, мгновенно разворачиваясь в точках 𝑥 = 0 и 𝑥 = 𝑠. В точке 𝑥1 находится Вася. Ему нужно попасть в точку 𝑥2. Он преодолевает 1 метр за 𝑡2 секунд. Вам нужно определить минимальное время, за которое Вася сможет добраться из точки 𝑥1 в точку 𝑥2, если известно, где находится шаттл и в каком направлении он едет в момент, когда Вася пришел в точку 𝑥1. Вася может неограниченное количество раз заходить в шаттл в любой момент времени, когда позиции его и шаттла совпадают. Точки, в которых Вася может заходить и выходить из шаттла, не обязательно целочисленные. Считайте, что любая высадка/посадка происходит мгновенно. Вася может произвольным образом перемещаться по прямой (но не быстрее, чем 1 метр за 𝑡2 секунд) или даже стоять на месте.

Входные данные В первой строке следуют три целых числа 𝑠, 𝑥1 и 𝑥2 (2 ≤ 𝑠 ≤ 1000, 0 ≤ 𝑥1, 𝑥2 ≤ 𝑠, 𝑥1 ≠ 𝑥2) — максимальная координата точки, до которой доезжает шаттл, точка, в которой находится Вася и точка, в которую ему нужно попасть. Во второй строке следуют два целых числа 𝑡1 и 𝑡2 (1 ≤ 𝑡1,𝑡2 ≤ 1000) — время в секундах, за которое шаттл преодолевает 1 метр, и время в секундах, за которое Вася преодолевает 1 метр. В третьей строке следуют два целых числа 𝑝 и 𝑑 (1 ≤ 𝑝 ≤ 𝑠 − 1, 𝑑 равняется 1 или −1) — позиция шаттла в момент, когда Вася пришел в точку 𝑥1, а также направление движения шаттла в этот же момент. Если 𝑑 = −1, то шаттл движется к метро (то есть в направлении от точки 𝑠 в точку 0). Если 𝑑 = 1, то шаттл движется к офису (то есть в направлении от точки 0 в точку 𝑠).

Выходные данные Выведите минимальное время в секундах, за которое Вася может добраться из точки 𝑥1 в точку 𝑥2.

Примеры

Входные данные

4 2 4

3 4

1 1

Выходные данные

Входные данные

5 4 0

1 2

3 1

Выходные данные

Примечание

В первом примере Васе выгоднее пойти пешком. Таким образом, ему нужно пройти 2 метра, и он сможет это сделать суммарно за 8 секунд, так как он преодолевает 1 метр за 4 секунды. Во втором примере он может, например, пойти в сторону точки 𝑥2 и дойти до точки с координатой 1 за 6 секунд (так как ему нужно пройти для этого 3 метра, а он преодолевает 1 метр за 2 секунды). В этот момент времени, шаттл также будет находиться в точке 1, поэтому Вася может зайти в него, и доехать оставшийся 1 метр за 1 секунду. Таким образом, Вася доберётся до точки 𝑥2 суммарно за 7 секунд.

Тип	Batch
Ограничение по времени	1 секунда
Ограничение по памяти	256 МБ
Команды компиляции	C++11 / g++	`/usr/bin/g++ -DEVAL -std=c++11 -O2 -pipe -static -s -o B B.cpp`

Задача C. Чаты

Для общения с коллегами Вася использует корпоративный мессенджер. Список чатов в нем работает стандартным образом: при отправке\получении сообщения чат с собеседником поднимается на самый верх списка. Относительный порядок всех остальных чатов при этом не изменяется. Если ранее чата с этим собеседником не было, то просто в верх списка чатов вставляется новый. Когда Вася только пришел в компанию, список его чатов, очевидно, был пуст. Вам нужно по истории сообщений построить список чатов Васи.

Входные данные

В первой строке записано целое число 𝑛 (1 ≤ 𝑛 ≤ 300 000) — количество сообщений. Далее в 𝑛 строках перечислены адресаты сообщений в порядке отправки\получения сообщений. Имя каждого адресата — непустая последовательность строчных букв английского алфавита длины не более 10.

Выходные данные

Выведите всех адресатов, с кем общался Вася, в порядке расположения чатов с ними сверху вниз.

Пример

Входные данные

alex

ivan

roman

ivan

Выходные данные

ivan

roman

alex

Входные данные

alina

maria

ekaterina

darya

ekaterina

maria

alina

Выходные данные

alina

maria

ekaterina

darya

Тип	Batch
Ограничение по времени	2 секунды
Ограничение по памяти	256 МБ
Команды компиляции	C++11 / g++	`/usr/bin/g++ -DEVAL -std=c++11 -O2 -pipe -static -s -o C C.cpp`