e-olymp
Змагання

December 18 - RMQ

Максимум

Ваша задача дуже проста і навіть без великої історії: просто потрібно знайти максимум на відрізку.

Вхідні дані

Спочатку подається кількість чисел n (1 n 105) у масиві. В наступному рядку задано n чисел – вихідний масив a1, a2, ..., an (-109ai109). Наступний рядок містить кількість запитів q (1 q 5·105). Кожний з наступних q рядків містить по два натуральні числа l та r (1 l, r n) – відрізок, на якому слід знайти максимум.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
10
5 1 2 8 7 6 10 7 5 6
8
1 10
5 10
1 5
2 6
2 3
7 7
7 8
5 9
Вихідні дані #1
10
10
8
8
2
10
10
10
Автор Остап Столярчук
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року