У вас есть массив \(a\) размера \(n\), состоящий только из нулей и единиц. Вы можете выполнять следующую операцию:
- выбрать два индекса \(1 \le i , j \le n\), \(i \ne j\),
- добавить \(a_{i}\) к \(a_{j}\),
- удалить \(a_{i}\) из \(a\).
Обратите внимание, что элементы \(a\) могут стать больше \(1\) после выполнения некоторых операций. Также обратите внимание, что после операции \(n\) становится на \(1\) меньше.
Какое минимальное количество операций необходимо, чтобы сделать \(a\) неубывающим, т. е. каждый элемент должен быть не меньше предыдущего?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для сортировки \(a\) в неубывающем порядке.
Примечание
В первом наборе входных данных \(a\) уже неубывающий, поэтому никаких операций выполнять не нужно, и ответ равен \(0\).
Во втором наборе входных данных можно выполнить операцию для \(i = 1\) и \(j = 5\), тогда \(a\) будет равно \([0, 0, 1, 2]\) и станет неубывающим.
В третьем наборе входных данных можно выполнить операцию для \(i = 2\) и \(j = 1\), так что \(a\) будет равно \([1]\) и станет неубывающим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
8
0 0 1 1 1 1 1 1
5
1 0 0 1 1
2
1 0
11
1 1 0 0 1 0 0 1 1 1 0
|
0
1
1
3
|