Відома команда ICPC знову
Коли пан Б, пан Г і пан М готувалися до фінального конкурсу ACM-ICPC 2012 року, пан Б зібрав велику кількість задач для їхнього щоденного тренування. Коли вони вирішували тренуватися, пан Б обирав одну з них із набору задач. Усі задачі в наборі були відсортовані за часом публікації. Кожного разу професор С, їхній тренер, казав їм обрати одну задачу, опубліковану в певному часовому інтервалі. Тобто, якщо задачі були відсортовані в рядок, кожного разу вони обирали одну з них із вказаного сегмента рядка.
Крім того, збираючи задачі, пан Б також знав оцінку складності кожної задачі. Коли його просили обрати задачу, якщо він обирав найлегшу, пан Г скаржився, що "Гей, яка тривіальна задача!"; якщо він обирав найважчу, пан М бурчав, що це займе занадто багато часу. Щоб вирішити цю дилему, пан Б вирішив обрати ту, що має середню складність. Тому йому потрібен був спосіб дізнатися медіанне число у заданому інтервалі послідовності.
Вхідні дані
Для кожного тестового випадку перший рядок містить одне ціле число n (1 ≤ n ≤ 100000), що вказує на загальну кількість задач. Другий рядок містить n цілих чисел x_i (0 ≤ x_i ≤ 1000000000), розділених одним пробілом, що позначають складність кожної задачі, вже відсортованих за часом публікації. Наступний рядок містить одне ціле число m (1 ≤ m ≤ 100000), що вказує на кількість запитів. Потім йдуть m рядків, кожен з яких містить пару цілих чисел, A і B (1 ≤ A ≤ B ≤ n), що означає, що пан Б повинен обрати задачу між позиціями A і B (включно, позиції рахуються з 1). Гарантовано, що кількість елементів між A і B є непарною.
Вихідні дані
Для кожного запиту виведіть один рядок, що містить ціле число, яке позначає складність задачі, яку пан Б повинен обрати.