Реалізуйте sqrt-декомпозицію запитів (алгоритм Мо) для знаходження медіани на відрізку.
Медіана - це елемент, який буде знаходитись в середині підмасиву, якщо всі числа на ньому відсортувати.
У випадку підмасива парної довжини, медіаною будемо вважати лівіший центральний елемент в відсортованому підмасиві.
Наприклад:
для підмасива (1,7,9,5,3) медіаною є 5 оскільки в відсортованому підмасиві (1,3,5,7,9) він буде стояти посередині.
для підмасива (1,7,9,3) медіаною є 3 оскільки в відсортованому підмасиві (1,3,7,9) посередині буде стояти 2 елемента: 3 та 7, але згідно умови ми приймемо за медіану лівіший

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 50000\)).
В другому рядку елементи масиву. (\(1 \le Ai \le 10^5\))
В третьому рядку вводиться число \(K\) - кількість запитів (\(1 \le K \le 30000\))
В кожному з наступних \(K\) рядків міститься по два числа - номера лівого і правого елементів відрізка масиву

Формат вихідних даних

Для кожного запиту виведіть через пробіл - відповідь на запит

Приклад вхідних даних

5
2 2 2 1 5 
2
3 5
4 5

Приклад вихідних даних

2 1