Петух Хей-Хей и камни
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На острове Мотунуи выросла популяция петухов, и теперь петух Хей-Хей с сородичами ищут себе пропитание.

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

Сейчас $$$n$$$ петухов стоят на прямой, на которой находятся $$$m$$$ камней. Они собираются действовать по следующему алгоритму: определяют камень с максимальной вкусностью и идут к нему по прямой. Тот петух, который дойдет первым, мгновенно съедает самый вкусный камень, и все петухи начинают идти к следующему по вкусности. Если петухи подходят к одному и тому же камню одновременно, то камень съедает петух с меньшим номером.

Для каждого камня определите, какой петух его съест.

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

В первой строке ввода дано целое число $$$n$$$ — количество петухов ($$$1 \le n \le 10^5$$$).

Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ — координаты петухов ($$$0 \le a_i \le 10^9$$$).

В третьей строке ввода дано целое число $$$m$$$ — количество камней ($$$1 \le m \le 10^5$$$).

Затем в $$$m$$$ следующих строках перечислены целые числа $$$k_i$$$ и $$$b_i$$$ — вкусность и координата камня соответственно ($$$1 \le k_i \le 10^9$$$; $$$0 \le b_i \le 10^9$$$).

Гарантируется, что для камней все координаты различны и все вкусности различны.

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

Выведите $$$m$$$ строк, в каждой строке число — номер петуха, который съест соответствующий камень.

Примеры

Входные данные
2
3 10
3
70 5
10 6
100 7
Выходные данные
1
2
2
Входные данные
1
5
4
10 11
5 9
6 10
4 100
Выходные данные
1
1
1
1