Задана полоска, разделенная на клетки, клетки пронумерованы слева направо от $$$0$$$ до $$$10^{18}$$$. Изначально все клетки белые.
Вы можете выполнять следующее действие: выбрать две белые клетки $$$i$$$ и $$$j$$$, такие что $$$i \ne j$$$ и $$$|i - j| \le k$$$, и покрасить их в черный цвет.
Задан список $$$a$$$. Все клетки из этого списка должны быть покрашены в чёрный. Также в черный цвет может быть покрашено не более одной клетки, не входящей в этот список. Ваша задача — определить, для какого минимального значения $$$k$$$ это возможно.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_i < 10^{18}$$$; $$$a_i < a_{i + 1}$$$).
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных выведите одно целое число — минимальное значение $$$k$$$, для которого возможно покрасить все заданные клетки.
421 21732 4 951 5 8 10 13
1 1 2 3
В первом наборе входных данных с параметром $$$k=1$$$ можно покрасить клетки $$$(1, 2)$$$.
Во втором наборе входных данных с параметром $$$k=1$$$ можно покрасить клетки $$$(7, 8)$$$.
В третьем наборе входных данных с параметром $$$k=2$$$ можно покрасить клетки $$$(2, 4)$$$ и $$$(8, 9)$$$.
В четвертом наборе входных данных с параметром $$$k=3$$$ можно покрасить клетки $$$(0, 1)$$$, $$$(5, 8)$$$ и $$$(10, 13)$$$.
Название |
---|