Вам задан массив из n целых чисел ai, а также m запросов. Каждый запрос описывается с помощью двух целых чисел (lj, rj).
Определим функцию 
. Функция определена только для u ≤ v.
Для каждого запроса выведите наибольшее значение функции f(ax, ay) по всем lj ≤ x, y ≤ rj, ax ≤ ay.
Выходные данные
Для каждого запроса выведите в отдельной строке целое число aj — наибольшее значение функции f(ax, ay) по всем lj ≤ x, y ≤ rj, ax ≤ ay.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1 2 3 4 5 6
1 6
2 5
3 4
|
7
7
7
|
|
2
|
1 1
1
1 1
|
1
|
|
3
|
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
|