Дано великий одновимірний масив (використані елементи з ~1~-го по ~N~-й). Для нього треба багаторазово відповідати на питання «який максимум серед усіх підряд елементів з ~j~-го по ~k~-й?».

Вхідні дані

У першому рядку задано кількість елементів у масиві ~N~ (~1 \leqslant N \leqslant 10^5~). У другому рядку задано ~N~ чисел — значення елементів масиву (кожне значення від ~0~ до ~10^9~). У третьому рядку задано кількість запитів ~Q~ (~1 \leqslant Q \leqslant 10^5~). У наступних ~Q~ рядках задано самі запити. Кожен запит являє собою пару чисел ~j~ та ~k~ (~1 \leqslant j \leqslant k \leqslant N~) і означає «знайти максимум серед усіх підряд елементів з ~j~-го по ~k~-й».

Результати

Вивести ~Q~ рядків, у кожному з яких міститься єдине число — максимум елементів для відповідного запиту.

Приклади

Вхід (приклад 1)

5
72 31 95 33 14
3
3 4
1 2
1 5

Результат (приклад 1)

95
72
95