Реалізуйте sparse table для знаходження максимального елемента на відрізку.

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

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

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

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

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

5
2 2 2 1 5
2
2 3
2 5

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

2 5