У Томми есть детская игрушка «cортировщик», с расположенными подряд
n колышками. На каждом колышке сейчас не более одного диска (то есть на каком-то колышке диск есть, а на каком-то его нет). Томми хочет переложить имеющиеся диски на колышках таким образом, чтобы они образовывали неубывающую последовательность при просмотре слева направо. То есть на каждом следующем колышке количество дисков должно быть не меньше, чем на предыдущем. Какое минимальное количество дисков Томми необходимо переложить?
Обратите внимание, что какие- то колышки по окончанию сортировки могут быть пустыми. Какие-то колышки могут содержать более 1 диска.
Входные данные
Программа получает на вход в первой строке целое число
n (1 <=
n <= 10
5), количество колышек на «cортировщике». Следующая строка содержит
n целых чисел
a1,
a2, ...
an – наличие диска на соответствующем колышке (0 <=
ai <= 1). число
0 означает, что на
i-м колышке нет диска,
1 – диск есть.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8
0 0 1 1 1 1 1 1
|
0
|
| 2 |
11
1 1 0 0 1 0 0 1 1 1 0
|
3
|