The Famous ICPC Team Again
Когда господа B, G и M готовились к финальному конкурсу ACM-ICPC 2012 года, господин B собрал обширный набор задач для их ежедневных тренировок. Каждый раз, когда они устраивали тренировку, господин B выбирал одну задачу из этого набора. Все задачи в наборе были отсортированы по времени их публикации. Профессор S, их тренер, просил их выбрать задачу, опубликованную в определённый временной интервал. Таким образом, если задачи были выстроены в ряд, каждый раз они выбирали одну из них из указанного сегмента.
Кроме того, при сборе задач господин B знал оценку сложности каждой задачи. Когда его просили выбрать задачу, если он выбирал самую лёгкую, господин G жаловался: "Эй, какая тривиальная задача!"; если он выбирал самую сложную, господин M ворчал, что на её решение уходит слишком много времени. Чтобы избежать этой дилеммы, господин B решил выбирать задачу средней сложности. Поэтому ему нужно было определить медианное значение в заданном интервале последовательности.
Входные данные
Для каждого тестового случая первая строка содержит одно целое число n (1 ≤ n ≤ 100000), обозначающее общее количество задач. Вторая строка содержит n целых чисел x_i (0 ≤ x_i ≤ 1000000000), разделённых пробелом, обозначающих сложность каждой задачи, уже отсортированных по времени публикации. Следующая строка содержит одно целое число m (1 ≤ m ≤ 100000), указывающее количество запросов. Затем следуют m строк, каждая из которых содержит пару целых чисел, A и B (1 ≤ A ≤ B ≤ n), обозначающих, что господин B должен выбрать задачу между позициями A и B (включительно, позиции считаются с 1). Гарантируется, что количество элементов между A и B нечётное.
Выходные данные
Для каждого запроса выведите одну строку, содержащую целое число, обозначающее сложность задачи, которую должен выбрать господин B.