Шкафчики с почти одинаковыми кодами

В школе у каждого шкафчика есть числовой код. Завхоз хочет найти два шкафчика с максимально похожими кодами: так проще проверять новые наклейки.

Под «похожестью» он понимает модуль разности кодов. Нужно узнать, какая наименьшая возможная разность получится, если выбрать два разных шкафчика.

Важно: коды могут быть большими по модулю (как 64-битные числа). В Python это не проблема.

Формат ввода

Первая строка: целое число n — количество шкафчиков (2 ≤ n ≤ 8000). Вторая строка: n целых чисел a1, a2, ..., an (-10^9 ≤ ai ≤ 10^9).

Формат вывода

Выведите одно целое число — минимальное значение |ai - aj| среди всех пар i ≠ j.

Ограничения

• 2 ≤ n ≤ 35000
• -10^9 ≤ ai ≤ 10^9
• По смыслу задачи числа могут выходить за 32-битный тип, ориентируйтесь на 64-битный.

Пример

Ввод:

5
10 3 21 8 14

Вывод:

2

Ключевое наблюдение: если числа отсортировать, то для любого элемента его «самый похожий» кандидат находится рядом. Почему? Между двумя не соседними числами в отсортированном списке есть хотя бы одно число посередине, а значит их разность не меньше разности какой-то соседней пары. Поэтому минимальный |ai - aj| всегда достигается на соседях после сортировки.

Приём: сортировка превращает поиск по всем парам (это O(n^2)) в один линейный проход по соседям.

План решения:

• Считай n и массив a.
• Отсортируй a по возрастанию.
• Инициализируй ответ разностью первых двух: best = a[1] - a[0].
• Пройди i от 1 до n-1 и обновляй best = min(best, a[i] - a[i-1]).
• Выведи best.

Мини-сниппет формулы (после сортировки): d = a[i] - a[i-1].

Сложность: сортировка O(n log n), проход O(n), память O(n).

Частая ошибка: пытаться проверять все пары (не пройдёт по времени) или забыть отсортировать и сравнивать «соседей во входе» — это не то же самое.