E. Бинарные инверсии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан бинарный массив$$$^{\dagger}$$$ длины $$$n$$$. Вам можете выполнить над ним следующую операцию не более одного раза. Операция заключается в следующем — вы можете выбрать любой элемент и инвертировать его: превратить $$$0$$$ в $$$1$$$ или наоборот.

Какое максимальное количество инверсий $$$^{\ddagger}$$$ может иметь массив после выполнения не более одной операции?

$$$^\dagger$$$ Бинарный массив — это массив, состоящий только из нулей и единиц.

$$$^\ddagger$$$ Количество инверсий в массиве — это количество пар индексов $$$i,j$$$ таких, что $$$i<j$$$ и $$$a_i > a_j$$$.

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

Входные данные состоят из нескольких наборов. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных в тесте. Далее следуют их описания.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — длину массива.

Следующая строка содержит $$$n$$$ целых положительных чисел $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$ ($$$0 \leq a_i \leq 1$$$) — элементы массива.

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

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

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

Пример
Входные данные
5
4
1 0 1 0
6
0 1 0 0 1 0
2
0 0
8
1 0 1 1 0 0 0 1
3
1 1 1
Выходные данные
3
7
1
13
2
Примечание

В первом примере инверсии изначально формируются парами индексов ($$$1, 2$$$), ($$$1, 4$$$), ($$$3, 4$$$), что в сумме составляет $$$3$$$, что уже является максимально возможным значением.

Во втором примере инверсии изначально образованы парами индексов ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$), в сумме четыре. Но, применив операцию над первым элементом, массив становится $$${1, 1, 0, 0, 1, 0}$$$, где инверсии уже образованы парами индексов ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 6$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$5, 6$$$), что в сумме составляет $$$7$$$ инверсий, что является максимально возможным.