Самые близкие дома

В городе Нумерград дома стоят вдоль одной прямой улицы. У каждого дома есть номер — целое число. Чем меньше разница номеров, тем ближе стоят дома.

Городскому планировщику нужно быстро найти, какая минимальная разница номеров встречается среди всех пар домов.

Формат ввода

В первой строке дано целое число n — количество домов. Во второй строке дано n целых чисел a1, a2, ..., an — номера домов.

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

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

Ограничения

• 2 ≤ n ≤ 20000
• 1 ≤ ai ≤ 1 000 000

Пример

Ввод:

5
10 3 20 7 8

Вывод:

1

В этом примере дома с номерами 7 и 8 стоят ближе всех.

Ключевое наблюдение: минимальная разница между двумя числами обязательно найдётся среди соседей в отсортированном массиве. Почему? Если x < y, а между ними в отсортированном списке есть число z, то y - x >= min(y - z, z - x). Значит, самая «тесная» пара не может быть разделена другими числами — она станет соседней после сортировки.

Приём: сортировка превращает задачу «проверить все пары» (их очень много) в линейный просмотр соседних элементов.

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

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

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

Частая ошибка: после сортировки не нужен модуль |ai - aj| — разность соседей a[i] - a[i-1] всегда неотрицательная. Ещё одна грабля — случай n = 2: его тоже покрывает инициализация из первых двух элементов.