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