Массив b называется хорошим, если не существует индексов 1 < i < j ≤ b таких, что bj - bi = 1. Вам дан целочисленный массив a1, a2, ..., a_n. Определите минимальное количество элементов, которые нужно удалить из данного массива, чтобы он стал хорошим

Добавлена: 28.04.2026
Обновлена: 28.04.2026
Предмет: Другое
Автор: Кэмп

Условие:

Массив `b` называется хорошим, если не существует индексов `1 < i < j ≤ |b|` таких, что `b_j - b_i = 1`.
Вам дан целочисленный массив `a_1, a_2, ..., a_n`. Определите минимальное количество элементов, которые нужно удалить из данного массива, чтобы он стал хорошим массивом.

Первая строка каждого набора содержит одно целое число `n` (`1 ≤ n ≤ 3 * 10^5`) — количество элементов в массиве.
Вторая строка каждого набора содержит `n` целых чисел `a_1, a_2, ..., a_n` (`1 ≤ a_i < n`) — элементы массива.

Для каждого набора данных выведите одно целое число — минимальное количество элементов, которые нужно удалить из массива, чтобы он стал хорошим.

Решение:

1. Условие задачи

Дан массив a. Он называется хорошим, если не существует индексов i и j таких, что
1 ≤ i < j ≤ |a| и a[j] - a[i] = 1.

То есть в массиве не должно быть двух чисел, различающихся на 1, стоящих в любом порядке (не обязательно подряд).

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

2. Переформулировка условия

Если в массиве есть два числа x и x+1 (в любых позициях), то это запрещённая пара.
Чтобы массив стал хорошим, нужно удалить все вхождения либо всех x, либо всех x+1 для каждой т...