Олимпиадный тренинг

Задача . F. Ксоры на подотрезке

Вам задан массив из n целых чисел a_i, а также m запросов. Каждый запрос описывается с помощью двух целых чисел (l_j, r_j).

Определим функцию $\text{[math]}$ . Функция определена только для u ≤ v.

Для каждого запроса выведите наибольшее значение функции f(a_x, a_y) по всем l_j ≤ x, y ≤ r_j, a_x ≤ a_y.

Входные данные

В первой строке находится пара целых чисел n, m (1 ≤ n ≤ 5·10⁴, 1 ≤ m ≤ 5·10³) — количество элементов в массиве a и количество запросов.

Во второй строке находятся n целых чисел a_i (1 ≤ a_i ≤ 10⁶) — элементы массива a.

В каждой из следующих m строк находится пара целых чисел l_j, r_j (1 ≤ l_j ≤ r_j ≤ n) — параметры j-го запроса.

Выходные данные

Для каждого запроса выведите в отдельной строке целое число a_j — наибольшее значение функции f(a_x, a_y) по всем l_j ≤ x, y ≤ r_j, a_x ≤ a_y.

Примеры

№

Входные данные

Выходные данные

6 3
1 2 3 4 5 6
1 6
2 5
3 4

7
7
7

1 1
1
1 1

6 20
10 21312 2314 214 1 322
1 1
1 2
1 3
1 4
1 5
1 6
2 2
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 5
5 6
6 6

	Кол-во
С++	5

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Нет