A. Mainak и массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 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)$$$, которое он может получить.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — длину массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 999$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

Для каждого набора входных данных выведите единственное целое число — максимальное значение $$$(a_n - a_1)$$$, которое Mainak может получить.

Пример
Входные данные
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
Примечание
  • В первом наборе входных данных мы можем сдвинуть подмассив с индекса $$$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$$$.