A. Максимумы на подотрезках

Дан массив и запросы: найти максимум на отрезке. Массив не меняется. Решите задачу корневой декомпозицией.

В первой строке - число $N$ ($1 \le N \le 10^5$).

Во второй - $N$ чисел от 1 до $10^5$.

В третьей - число запросов $K$ ($1 \le K \le 30\,000$), далее $K$ строк с парами $l$ и $r$ (нумерация с единицы).

Для каждого запроса выведите максимум на отрезке.