Ulduzlararası Ticarət
Nadir, Komandir Siskoya onun mürəkkəb testlərindən birini uğurla keçdiyi üçün mükafat olaraq Q təklif edib: Bajoran qurd dəliyinin hər iki ucunu (və əlbəttə ki, Deep Space Nine ilə birlikdə) köçürmək imkanı. Komandir köçürmə üçün təkliflər istəyib və müxtəlif tacirlər qurd dəliyinin uclarını ticarətləri ilə məşhur olan planetlər arasında keçid vaxtını azaltmaq üçün məlum kosmosa köçürmək istəyirlər. Sizin vəzifəniz qurd dəliyinin uclarını elə yerləşdirməkdir ki, bu planetlərdən hər hansı bir cüt arasında maksimum məsafə minimum olsun.
Sadəlik üçün, maraq doğuran bütün planetlər düz bir xətt üzərində yerləşir və qurd dəliyi olmadıqda, onların hər hansı bir cütü arasındakı məsafə sadəcə düz xətt məsafəsidir. Qurd dəliyi əlavə edildikdən sonra, səyahətçi bir planetdən birbaşa qurd dəliyinin bir ucuna gedə və sonra qurd dəliyinin digər ucundan digər planetə birbaşa gedə bilər. Bu halda səyahət edilən məsafə bu iki məsafənin cəmidir (qurd dəliyinin iki ucu arasında səyahət ani baş verir). Qeyd edək ki, səyahətçi həmişə qurd dəliyindən istifadə etməmək seçiminə malikdir, hətta qurd dəliyinin bir ucu maraq doğuran iki planetin arasında birbaşa yerləşsə belə. Nəhayət, qurd dəliyinin ucunu istənilən planetə çox yaxın yerləşdirə bilərsiniz ki, planetdən qurd dəliyinə olan məsafə faktiki olaraq sıfır olsun.
Giriş verilənləri
Giriş bir tam ədəd T (1 ≤ T ≤ 50) ilə başlayır ki, bu da test hallarının sayını göstərir. Hər bir test halı bir tam ədəd N (2 ≤ N ≤ 4000) ilə başlayır ki, bu da planetlərin sayını göstərir. Bu, hər biri bir tam ədəd x_i (-10^9 ≤ x_i ≤ 10^9) olan N sətirlə davam edir ki, bu da planet i-nin yerini göstərir (bütün planetlər x-oxu üzərində nöqtələrdir). Heç bir iki planet eyni yerdə olmayacaq.
Çıxış verilənləri
Hər bir test halı üçün qurd dəliyi elə yerləşdirildikdən sonra planetlərin hər hansı bir cütü arasında maksimum məsafəni bir sətirdə çap edin ki, bu dəyər minimum olsun. Əgər bu məsafə kəsrdirsə, onu növbəti tam ədədə yuvarlaqlaşdırın. Qeyd edək ki, bütün planet yerləri tam ədədlərlə verilsə də, qurd dəliyinin yeri tam ədəd koordinatlarına malik olmaya bilər.