1. Идея

Нужно выбрать две частоты, разность между которыми минимальна.

Прямой перебор всех пар слишком дорогой: пар n * (n - 1) / 2, а при n до 2 * 10^5 это уже слишком много.

Ключевая идея: сначала отсортировать все частоты. После сортировки самые близкие по значению элементы обязательно окажутся рядом.

Значит, достаточно проверить только соседние элементы в отсортированном массиве и выбрать пару с минимальной разностью.

2. Наблюдения

Наблюдение 1

Если массив отсортирован, то для любого элемента ближайший к нему по значению кандидат находится среди соседей.

Например, в отсортированном массиве

-10, -3, 5, 8, 20

если рассматривать число 5, то нет смысла сравнивать его с 20, пока не проверены соседи -3 и 8, потому что все более далёкие элементы отличаются не меньше.

Наблюдение 2

Минимальная разность среди всех пар в отсортированном массиве достигается на некоторой соседней паре.

Почему так? Пусть есть два элемента a[i] и a[j], где i < j, и между ними есть хотя бы один элемент. Тогда

a[j] - a[i]

равно сумме нескольких соседних разностей:

(a[i+1] - a[i]) + (a[i+2] - a[i+1]) + ... + (a[j] - a[j-1])

Значит, хотя бы одна из этих соседних разностей не больше, чем разность a[j] - a[i]. Следовательно, искать ответ среди несоседних элементов не нужно.

Наблюдение 3

Если есть одинаковые числа, то их разность равна 0, а это уже наименьшая возможная разность. Значит, такая пара сразу является оптимальной.

После сортировки одинаковые элементы тоже будут стоять рядом.

3. Алгоритм

1. Считать n и массив частот a.
2. Отсортировать массив.
3. Считать, что пока лучший ответ — это первая соседняя пара:
   • best_u = a[0]
   • best_v = a[1]
   • best_diff = a[1] - a[0]
4. Пройти по всем соседним парам:
   • для каждого i от 0 до n - 2
   • вычислить diff = a[i + 1] - a[i]
   • если diff < best_diff, обновить ответ
5. Вывести best_u и best_v

После сортировки гарантируется, что a[i] <= a[i+1], поэтому вывод автоматически будет в нужном порядке u <= v.

4. Почему это работает

Докажем корректность.

После сортировки массив имеет вид:

a[0] <= a[1] <= ... <= a[n-1]

Рассмотрим любую пару элементов a[i] и a[j], где i < j.

Случай 1: j = i + 1

Это соседняя пара. Алгоритм её проверит.

Случай 2: j > i + 1

Тогда между a[i] и a[j] есть другие элементы. Разность между ними равна сумме соседних разностей на отрезке от i до j:

a[j] - a[i] = (a[i+1] - a[i]) + (a[i+2] - a[i+1]) + ... + (a[j] - a[j-1])

Все слагаемые неотрицательны. Значит, хотя бы одно из них не больше всей суммы. То есть существует такой индекс k, что

a[k+1] - a[k] <= a[j] - a[i]

Получается, для любой пары найдётся соседняя пара с разностью не больше.

Следовательно, минимальная разность среди всех пар обязательно достигается среди соседних элементов отсортированного массива.

Алгоритм перебирает все соседние пары и выбирает среди них минимальную, значит, он находит правильный ответ.

5. Сложность

Сортировка работает за O(n log n).

Проход по соседним парам занимает O(n).

Итоговая сложность: O(n log n).

Дополнительная память:

• сортировка массива и хранение чисел — O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long best_u = a[0];
    long long best_v = a[1];
    long long best_diff = a[1] - a[0];

    for (int i = 0; i < n - 1; i++) {
        long long diff = a[i + 1] - a[i];
        if (diff < best_diff) {
            best_diff = diff;
            best_u = a[i];
            best_v = a[i + 1];
        }
    }

    cout << best_u << ' ' << best_v << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

a.sort()

best_u = a[0]
best_v = a[1]
best_diff = a[1] - a[0]

for i in range(n - 1):
    diff = a[i + 1] - a[i]
    if diff < best_diff:
        best_diff = diff
        best_u = a[i]
        best_v = a[i + 1]

print(best_u, best_v)