Задача №114966. Объединение чисел
Дан массив натуральных чисел \(a_1, a_2, \ldots, a_n\), в котором хотя бы одно число встречается хотя бы два раза. За одну операцию вы можете выбрать любое число \(x\) из массива и удалить все вхождения числа \(x\) в массив. Найдите минимальное число операций, которое необходимо применить к массиву, чтобы в нём были два подряд идущих равных числа.
Можно показать, что если в массиве изначально было \(2\) равных числа, то данными операциями можно получить массив, в котором условие выполняется.
Первая строка содержит единственное целое число \(n\) (\(2 \le n \le 200\,000\)) — длина массива.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — элементы массива. Существуют такие \(1 \le i < j \le n\), что \(a_i=a_j\).
В первой строке выведите одно число \(m\) — минимальное число операций.
Далее выведите \(m\) строк. \(i\)-я строка должна содержать единственное число \(x_i\) — число, выбранное в \(i\)-й операции.
Если есть несколько оптимальных решений, можно вывести любое из них.
В первом примере после удаления всех вхождений числа \(2\) в массив, он станет равным \([1, 3, 1]\). Далее после удаления числа \(3\) из массива он станет равным \([1, 1]\), что удовлетворяет условию. Можно показать, что желаемого результата нельзя достичь за меньше чем \(2\) операции.
Во втором тесте уже есть пара равных соседних чисел.
Тесты к этой задаче состоят из 7 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 12 | \(n \le 10\) | – | 0 | |
| 2 | 13 | \(n \le 100\) | – | 0, 1 | |
| 3 | 17 | \(n \le 1000\) | – | 0, 1, 2 | |
| 4 | 8 | \(n \le 5000\) | – | 0, 1, 2, 3 | |
| 5 | 21 | – | – | – | В массиве не более 2 различных значений. |
| 6 | 13 | – | \(a_i \le 10\) | – | |
| 7 | 16 | – | – | 0 – 6 | |
5 1 2 3 1 2
2 2 3
4 1 2 2 1
0