21/11/2024 20:59:48

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2614. Изменение последовательности

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дана последовательность из `N` элементов `A_1, A_2, ..., A_N`.
Необходимо изменить последовательность таким образом, чтобы выполнялось `A_i != i` для всех
`i` от 1 до `N`.

Для изменения последовательности применяется следующая операция:

Выбирается некоторый элемент последовательности и перед ним вставляется число 0. Например, после вставки 0 перед 3-м элементом из
последовательности [3,2,4,2] получается последовательность [3,2,0,4,2].

Первая строка ввода содержит одно целое число `N` (`1<= N <= 10^5`) -- начальное количество элементов в последовательности.
Вторая строка ввода `N` целых чисел в диапазоне от 1 до `10^6` -- элементы последовательности.

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

```sample Пример ввода
4
3 2 4 2
```

```sample Пример вывода
2
```
Можно вставить 0 перед 1-м элементом, получив последовательность [0,3,2,4,2],
а затем перед 4-м элементом последовательности, получив [0,3,2,0,4,2].