В старом отеле есть очень длинный коридор из \(n\) комнат. Отель полностью заполнен, и в каждой комнате уже живёт некоторое количество людей.
У управляющего была странная привычка. Он следил за тем, чтобы в следующей комнате жило не меньше людей, чем в любой из предыдущих. При этом он всегда подписывал, сколько человек он заселил в ту или иную комнату. Со временем свободных номеров не осталось, и гости перестали прибывать.
Однажды в отель приехал инспектор. Для отчёта инспектору нужно проверить \(t\) комнат. Каждый раз он будет называть число \(x\). Ваша задача — найти самую правую комнату, в которой живёт ровно \(x\) человек. Если такой комнаты в отеле не окажется, инспектор ставит прочерк в отчёте и продолжает проверку.
Формат входных данных
В первой строке записано целое число \(n\ (1 \le n \le 500000)\) — количество комнат в отеле. Во второй строке записаны \(n\) целых чисел \(a_0, a_1, \ldots, a_{n-1}\), отсортированных по неубыванию — количество человек в каждой комнате. В третьей строке записано целое число \(t\ (1 \le t \le 10000)\) — количество запросов на поиск комнаты. В следующих \(t\) строках записано по одному целому числу \(x\ (x \le 10^9)\) — количество человек в комнате, которую ищет инспектор.
Формат выходных данных
Для каждого из \(t\) запросов выведите одно целое число — индекс комнаты (нумерация с нуля), в которой количество человек равно \(x\). Если такой комнаты не существует, выведите −1.
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 4 4 4 7
1
4
|
4
|