У Mainak есть массив \(a_1, a_2, \ldots, a_n\) из \(n\) положительных целых чисел. Он сделает следующую операцию с данным массивом ровно один раз:
- Выбрать подотрезок массива и циклически сдвинуть его на любую величину.
Формально, он может сделать следующее ровно один раз:
- Выбрать целые числа \(l\) и \(r\) такие, что \(1 \le l \le r \le n\) и любое целое неотрицательное число \(k\).
- Повторить \(k\) раз: установить \(a_l=a_{l+1}, a_{l+1}=a_{l+2}, \ldots, a_{r-1}=a_r, a_r=a_l\) (все изменения происходят одновременно).
Mainak хочет максимизировать значение \((a_n - a_1)\) после применения ровно одной такой операции. Определите максимальное значение \((a_n - a_1)\), которое он может получить.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — максимальное значение \((a_n - a_1)\), которое Mainak может получить.
Примечание
- В первом наборе входных данных мы можем сдвинуть подмассив с индекса \(3\) до индекса \(6\) на \(2\) (т.е.. выбрать \(l = 3\), \(r = 6\) и \(k = 2\)), чтобы получить оптимальный массив: \(\)[1, 3, \underline{9, 11, 5, 7}] \longrightarrow [1, 3, \underline{5, 7, 9, 11}]\(\) Тогда ответ равен \(a_n - a_1 = 11 - 1 = 10\).
- Во втором наборе входных данных оптимально сдвинуть подмассив, начинающийся и заканчивающийся в индексе \(1\), на величину \(2\).
- В четвёртом наборе входных данных оптимально сдвинуть подмассив с индекса \(1\) до индекса \(4\) на величину \(3\). Тогда ответ равен \(8 - 1 = 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
6
1 3 9 11 5 7
1
20
3
9 99 999
4
2 1 8 1
3
2 1 5
|
10
0
990
7
4
|