Помимо теории чисел и строковых алгоритмов Профессор Ш. любит заниматься массивами, но не простыми, а отсортированными по неубыванию элементов. Сегодня Профессор Ш. придумал отличную задачу и делится её формулировкой с вами.
Изначально имеется массив $$$a$$$, состоящий из $$$N$$$ чисел, элементы которого расположены в порядке неубывания. К данному массиву можно применять запросы $$$2$$$ типов:
Так как Профессор Ш. умеет работать только с отсортированными массивами, он не всегда умеет проверять, есть ли в массиве число $$$x$$$. Помогите Профессору – напишите программу, которая будет верно отвечать на запросы обоих типов.
В первой строке содержится число $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – количество элементов массива.
Во второй строке содержатся $$$N$$$ чисел $$$a_i$$$ $$$(-10^{18} \le a_i \le 10^{18})$$$ – элементы массива $$$a$$$. Гарантируется, что изначально элементы массива отсортированы по неубыванию.
В третьей строке содержится число $$$Q$$$ $$$(1 \le Q \le 3 \cdot 10^5)$$$ – количество запросов.
В следующих $$$Q$$$ строках содержатся запросы. Запросы задаются следующим образом:
Для каждого запроса вида «$$$?~x$$$» выведите в отдельной строке число – номер числа $$$x$$$ в массиве. Если числа $$$x$$$ в масиве нет, в отдельной строке выведите «$$$-1$$$». Считается, что элементы массива нумеруются с $$$1$$$.
7 1 2 3 4 5 6 7 7 ? 9 s 2 ? 4 s -2 ? 3 s -5 ? 6
-1 6 3 1
7 1 1 2 2 3 3 4 7 ? 9 s 2 ? 4 s -1 ? 2 s -5 ? 1
-1 2 4 4
Рассмотрим первый пример.
Изначально массив $$$a = [1, 2, 3, 4, 5, 6, 7]$$$.
