E. Лучшее время для покупки и продажи акций
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Красота массива $$$b$$$ длины $$$m$$$ (где $$$m \ge 2$$$) определяется как максимальное значение $$$b_j - b_i$$$ для всех пар индексов $$$i$$$ и $$$j$$$ таких, что $$$1\le i \lt j\le m$$$. Формально, она равна $$$\max\limits_{1\le i \lt j\le m} (b_j - b_i)$$$. Обратите внимание, что красота может быть отрицательной, если массив является строго убывающим.

Хао и Алекс играют в пошаговую игру на массиве $$$a$$$ длины $$$n$$$. Изначально все элементы массива разблокированы. Игроки поочередно делают ходы, при этом Хао ходит первым.

  • Хао в свой ход выбирает один разблокированный элемент из массива $$$a$$$ и удаляет его.
  • Алекс в свой ход выбирает один разблокированный элемент из массива $$$a$$$ и блокирует его (так что Хао его больше не может удалить).

Игра продолжается до тех пор, пока все элементы массива $$$a$$$ не будут либо заблокированы, либо удалены. Можно доказать, что игра длится ровно $$$n$$$ ходов, и ровно $$$\left\lfloor \frac{n}{2} \right\rfloor$$$ элементов останутся заблокированными в массиве $$$a$$$ в конце.

Хао хочет минимизировать красоту конечного массива заблокированных элементов, в то время как Алекс хочет максимизировать её. Определите красоту конечного массива, если оба игрока играют оптимально.

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

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

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

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

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

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

Для каждого набора входных данных выведите одно целое число — красоту конечного массива, если Хао и Алекс играют оптимально.

Пример
Входные данные
6
5
5 1 2 3 4
4
3 1 2 1
10
7 1 3 5 8 2 8 3 5 1
6
1 1 4 5 1 4
9
9 9 8 2 4 4 3 5 3
4
1000000000 1 2 3
Выходные данные
1
-2
5
3
1
-999999998
Примечание

В первом наборе входных данных игра может проходить следующим образом. Выделенные жирным элементы заблокированы Алексом:

  • Ход 1 (Хао): Удалить элемент $$$1$$$ (на позиции $$$2$$$), в результате чего получается $$$[5, 2, 3, 4]$$$.
  • Ход 2 (Алекс): Заблокировать элемент $$$3$$$ (на позиции $$$3$$$), в результате чего получается $$$[5, 2, \mathbf{3}, 4]$$$.
  • Ход 3 (Хао): Удалить элемент $$$2$$$ (на позиции $$$2$$$), в результате чего получается $$$[5, \mathbf{3}, 4]$$$.
  • Ход 4 (Алекс): Заблокировать элемент $$$4$$$ (на позиции $$$3$$$), в результате чего получается $$$[5, \mathbf{3}, \mathbf{4}]$$$.
  • Ход 5 (Хао): Удалить элемент $$$5$$$ (на позиции $$$1$$$), в результате чего получается $$$[\mathbf{3}, \mathbf{4}]$$$.

Красота конечного массива $$$b = [3, 4]$$$ равна $$$b_2 - b_1 = 4 - 3 = 1$$$.

Во втором наборе входных данных обратите внимание, что ответ может быть отрицательным:

  • Ход 1 (Хао): Удалить элемент $$$2$$$ (на позиции $$$3$$$), в результате чего получается $$$[3, 1, 1]$$$.
  • Ход 2 (Алекс): Заблокировать элемент $$$1$$$ (на позиции $$$2$$$), в результате чего получается $$$[3, \textbf{1}, 1]$$$.
  • Ход 3 (Хао): Удалить элемент $$$1$$$ (на позиции $$$3$$$), в результате чего получается $$$[3, \textbf{1}]$$$.
  • Ход 4 (Алекс): Заблокировать элемент $$$3$$$ (на позиции $$$1$$$), в результате чего получается $$$[\textbf{3}, \textbf{1}]$$$.

Красота конечного массива $$$b = [3, 1]$$$ равна $$$b_2 - b_1 = 1 - 3 = -2$$$.

В третьем наборе входных данных один из возможных конечных массивов (при условии оптимальной игры обоих игроков) это $$$b = [3, 5, 8, 5, 1]$$$. Красота, которая является максимальной разницей $$$b_j - b_i$$$ для всех пар индексов $$$i$$$ и $$$j$$$ таких, что $$$1\le i \lt j\le 5$$$, равна $$$b_3 - b_1 = 8 - 3 = 5$$$.