Бинарный поиск

Условие

В первой строке дано n, во второй — n целых чисел, отсортированных по неубыванию. В третьей строке дано q — число запросов, в каждой из следующих q строк — одно число x. Для каждого запроса выведите в отдельной строке индекс (с 1) первого вхождения x в массив или -1, если его нет.

Примеры

5
1 3 5 7 9
3
5
1
4

3
1
-1

6
2 2 2 5 8 8
3
2
8
7

1
5
-1

Ограничения

• 1 ≤ n, q ≤ 10^5
• -10^9 ≤ a_i, x ≤ 10^9