B. Восстание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ размера $$$n$$$, состоящий только из нулей и единиц. Вы можете выполнять следующую операцию:

  • выбрать два индекса $$$1 \le i , j \le n$$$, $$$i \ne j$$$,
  • добавить $$$a_{i}$$$ к $$$a_{j}$$$,
  • удалить $$$a_{i}$$$ из $$$a$$$.

Обратите внимание, что элементы $$$a$$$ могут стать больше $$$1$$$ после выполнения некоторых операций. Также обратите внимание, что после операции $$$n$$$ становится на $$$1$$$ меньше.

Какое минимальное количество операций необходимо, чтобы сделать $$$a$$$ неубывающим, т. е. каждый элемент должен быть не меньше предыдущего?

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следует их описание.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$), размер массива $$$a$$$.

Следующая строка содержит $$$n$$$ целых чисел $$$a_{1}, a_{2}, \ldots a_{n}$$$ ($$$a_i$$$ равно $$$0$$$ или $$$1$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для сортировки $$$a$$$ в неубывающем порядке.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$a$$$ уже неубывающий, поэтому никаких операций выполнять не нужно, и ответ равен $$$0$$$.

Во втором наборе входных данных можно выполнить операцию для $$$i = 1$$$ и $$$j = 5$$$, тогда $$$a$$$ будет равно $$$[0, 0, 1, 2]$$$ и станет неубывающим.

В третьем наборе входных данных можно выполнить операцию для $$$i = 2$$$ и $$$j = 1$$$, так что $$$a$$$ будет равно $$$[1]$$$ и станет неубывающим.