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

Вам дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел.

За одну операцию вы выбираете два индекса $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$). Затем отрезок $$$a_l, a_{l+1}, \ldots, a_r$$$ разворачивается, и каждое значение в этом отрезке удваивается.

Иными словами, после применения операции выбранный отрезок становится $$$2\cdot a_r, 2\cdot a_{r-1}, \ldots, 2\cdot a_l$$$, а весь массив принимает вид $$$$$$[a_1, a_2, \ldots, a_{l-1}, 2\cdot a_r, 2\cdot a_{r-1}, \ldots, 2\cdot a_l, a_{r+1}, \ldots, a_n].$$$$$$

Значение разрыва массива — это максимальное значение $$$|a_i-a_{i+1}|$$$ по всем $$$1 \le i \lt n$$$.

Найдите минимально возможное значение разрыва массива $$$a$$$ после применения не более одной операции.

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

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

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

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

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

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

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

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

В первом наборе входных данных оптимально выбрать $$$l = 4$$$ и $$$r = 5$$$. Получившийся массив: $$$$$$[9, 9, 8, \mathbf{8}, \mathbf{4}, 4, 3, 5, 3]$$$$$$ и получившееся значение разрыва равно $$$4$$$, оно достигается при $$$i = 4$$$.

Во втором наборе входных данных значение разрыва до применения каких-либо операций равно $$$1$$$. Можно показать, что применение любой операции увеличит это значение, поэтому ответ равен $$$1$$$.