На острове Мотунуи выросла популяция петухов, и теперь петух Хей-Хей с сородичами ищут себе пропитание.
Как известно, петухи острова не отличаются умом и сообразительностью, а потому питаются камнями, причем каждый из камней характеризуется своей вкусностью $$$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$$$ строк, в каждой строке число — номер петуха, который съест соответствующий камень.
23 10370 510 6100 7
1 2 2
15410 115 96 104 100
1 1 1 1