1. Идея

Нужно найти не просто второй элемент по позиции, а второй по величине различный балл.

Например, для массива 7 7 3 ответ равен 3, потому что максимальный различный балл — 7, а следующий за ним — 3.

Самая удобная идея — за один проход поддерживать:

• mx1 — наибольшее различное значение среди уже просмотренных,
• mx2 — второе по величине различное значение среди уже просмотренных.

При обработке каждого нового числа x:

• если x больше текущего максимума mx1, то старый mx1 становится кандидатом на mx2, а x становится новым mx1;
• иначе, если x меньше mx1, но больше текущего mx2, то x улучшает второй максимум.

Так мы сразу получим ответ за один проход без сортировки.

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

Наблюдение 1

Нас интересуют только два наибольших различных значения.

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

Например:

• 10 10 10 4 → ответ 4
• 5 3 5 2 3 → ответ 3

Наблюдение 2

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

Поэтому обновление mx2 происходит только при условии x < mx1.

Наблюдение 3

Нужно аккуратно работать с начальными значениями, потому что баллы могут быть отрицательными. Поэтому в эталонном решении используются флаги:

• has1 — уже найден ли первый максимум,
• has2 — уже найден ли второй максимум.

Это позволяет не опираться на какие-то специальные "очень маленькие" числа.

3. Алгоритм

Будем последовательно читать все числа и поддерживать mx1, mx2, has1, has2.

Для каждого x:

1. Если первый максимум ещё не найден (not has1) или x > mx1:

   • если mx1 уже был найден, то старый mx1 становится новым mx2;
   • затем присваиваем mx1 = x;
   • отмечаем, что первый максимум найден.

2. Иначе, если x < mx1 и при этом:

   • второй максимум ещё не найден, или
   • x > mx2,

   то присваиваем mx2 = x и отмечаем, что второй максимум найден.

После обработки всех чисел выводим mx2.

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

Докажем, что после обработки всех элементов:

• mx1 — это максимальное различное значение,
• mx2 — это второе по величине различное значение.

Рассмотрим, что поддерживают переменные после каждого шага.

Что хранит mx1

Если встречается число больше текущего mx1, мы обновляем mx1.
Значит, после просмотра некоторого префикса массива mx1 всегда равен наибольшему числу в этом префиксе.

Что хранит mx2

mx2 обновляется только тогда, когда число:

• строго меньше mx1, то есть отличается от максимума;
• при этом больше текущего mx2, если второй максимум уже был найден.

Значит, mx2 всегда является наибольшим из всех просмотренных чисел, которые строго меньше mx1.

Это и есть второй по величине различный элемент.

Почему перенос старого mx1 в mx2 корректен

Если пришло новое число x, такое что x > mx1, то старый mx1 становится меньше нового максимума.
При этом старый mx1 был самым большим среди всех предыдущих чисел, значит теперь он естественно становится лучшим кандидатом на второе место.

Поэтому присваивание:

• mx2 = mx1
• mx1 = x

полностью корректно.

Почему одинаковые максимумы не мешают

Если x == mx1, то число не должно попасть в mx2, ведь нужен второй различный максимум.
Именно поэтому во второй ветке стоит условие x < mx1.

Таким образом, одинаковые максимальные значения просто игнорируются как кандидаты на второе место.

Итог

После одного прохода по массиву:

• mx1 — наибольший различный балл,
• mx2 — второй по величине различный балл.

Так как по условию гарантируется наличие хотя бы двух различных значений, ответ всегда существует.

5. Сложность

Каждое число обрабатывается ровно один раз.

• Время: O(n)
• Память: O(1)

6. Код на C++17

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

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

    long long mx1 = 0, mx2 = 0;
    bool has1 = false, has2 = false;

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;

        if (!has1 || x > mx1) {
            if (has1) {
                mx2 = mx1;
                has2 = true;
            }
            mx1 = x;
            has1 = true;
        } else if (x < mx1 && (!has2 || x > mx2)) {
            mx2 = x;
            has2 = true;
        }
    }

    cout << mx2 << "\n";
    return 0;
}

7. Код на Python 3

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

has1 = False
has2 = False
mx1 = 0
mx2 = 0

for x in a:
    if not has1 or x > mx1:
        if has1:
            mx2 = mx1
            has2 = True
        mx1 = x
        has1 = True
    elif x < mx1 and (not has2 or x > mx2):
        mx2 = x
        has2 = True

print(mx2)