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

Дан массив $$$a$$$ длины $$$n$$$. Вы можете выбрать любой подотрезок $$$a_l, a_{l + 1}, \ldots, a_r$$$ массива длины, не совпадающий со всем массивом, то есть, для которого $$$1 \le l \le r \le n$$$ и $$$r - l + 1 < n$$$. Красотой выбранного подоторезка назовем значение

$$$$$$\max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}).$$$$$$

Найдите максимальную красоту подотрезка среди всех возможных допустимых подотрезков массива (за исключением всего массива).

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ $$$(4 \leq n \leq 10^5)$$$ — длину массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_{i} \leq 10^9$$$) — элементы данного массива.

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

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

Для каждого набора входных данных выведите одно число — искомое максимальное значение красоты.

Пример
Входные данные
4
8
1 2 2 3 1 5 6 1
5
1 2 3 100 200
4
3 3 3 3
6
7 8 3 1 1 8
Выходные данные
9
297
0
14
Примечание

В первом тесте из условия оптимально выбрать отрезок $$$l = 7$$$, $$$r = 8$$$. Красота этого отрезка равна $$$(6 - 1) + (5 - 1) = 9$$$.

Во втором тесте из условия оптимально выбрать отрезок $$$l = 2$$$, $$$r = 4$$$. Красота этого отрезка равна $$$(100 - 2) + (200 - 1) = 297$$$.