Runda 21 - Bloki

Zawody stałe, runda 21

Limit czasowy: 3s; Limit pamięciowy: 32MB;

Bloki

Paweł i Władek mieszkają w bardzo małej miejscowości (składa się ona z jednego dużego ronda przy którym od zewnętrznej strony stoją bloki mieszkalne). Każdy blok ma ustaloną wysokość, bloki są rozstawione równomiernie wzdłuż ronda. Chłopcy ostatio się pokłócili, i postanowili zamieszkać od siebie maksymalnie daleko. Odległość mierzą tak: przejście z piętra na piętro to jedna jednostka czasu, tyle samo trwa przejście z bloku do bloku. Pomóż im znaleźć tę maksymalną odległość.

Wejście

W pierwszej linii, jedna liczba 1≤n≤10, liczba testów. W kolejnych n liniach, opisy kolejnych testów: wpierw, 1 ≤ k≤ 10 ⁵, liczba bloków. Kolejne k liczb to w₁,...,w_k, wysokości kolejnych bloków, podawane zgodnie z ruchem wskazówek zegara. Każda wysokość spełnia 1≤w≤10⁹

Wyjście

Dla każdego testu podaj jedną wartość - maksymalną odległość w jakiej mogą od siebie zamieszkać.

Test przykładowy

Wejście:

Wyjście:

Wyjaśnienie: W pierwszym przypadku przykładem maksymalnego rozwiązania jest zamieszkanie na 2 piętrze bloku 2 i na 4 piętrze bloku 4. W drugim - 2 piętro bloku 1 i parter bloku 1.