Однажды программист Алексей из Яндекса взял отпуск и уехал отдыхать на море. В один из дней он пошёл на пляж, причём пошёл туда не один. Возможно, он пошёл туда с мамой, возможно, с бабушкой, а, возможно, с другом или подругой. Важно, что пошёл он туда не один.
На пляже программист Алексей обнаружил, что осталось всего $$$n$$$ ($$$2 \leq n \leq 10^6$$$) свободных лежаков. Но среди всего этого множества лежаков программисту Алексею нужно было всего лишь 2: для него самого и для того (или той), с кем он пришёл. Так как программист Алексей очень любил порядок, то он хотел, чтобы лежаки были как можно более похожи друг на друга. Похожесть лежаков можно вычислить следующим образом:
Помогите программисту Алексею понять, какого минимального значения непохожести лежаков он может достичь, сравнив попарно все свободные лежаки.
В первой строке задано число $$$T$$$ ($$$1 \leq T \leq 1000$$$) – количество тестов. Каждый тест состоит из двух строк.
В первой строке каждого теста задано число $$$n$$$ ($$$2 \leq n \leq 10^6$$$) – количество лежаков.
Во второй строке каждого теста заданы $$$n$$$ чисел $$$a_i$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq a_i \leq 10^9$$$) – значения, которые были поставлены лежакам в соответствие по внешним признакам.
Сумма $$$n$$$ по всем тестам не превосходит $$$10^6$$$.
Для каждого теста выведите по одной строке, в которой должно быть единственное число – минимальное значение непохожести.
1 5 1 2 4 8 16
3
2 2 2 4 4 2 4 6 8
6 2
В первом примере Алексей выберет лежаки со значениями 1 и 2.
В первой части второго примера Алексей может взять только лежаки со значениями 2 и 4. Во второй части он выберет лежаки со значениями 4 и 6.
| Contest for Yandex interns 2019 |
|---|
| Finished |
