F. Ксоры на подотрезке
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Определим функцию . Функция определена только для u ≤ v.

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

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

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

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

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

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

Для каждого запроса выведите в отдельной строке целое число aj — наибольшее значение функции f(ax, ay) по всем lj ≤ x, y ≤ rj,  ax ≤ ay.

Примеры
Входные данные
6 3
1 2 3 4 5 6
1 6
2 5
3 4
Выходные данные
7
7
7
Входные данные
1 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
Выходные данные
10
21313
21313
21313
21313
21313
21312
21313
21313
21313
21313
2314
2315
2315
214
215
323
1
323
322