CF1760E.Binary Inversions

You are given a binary array$^{\dagger}$ of length $n$. You are allowed to perform one operation on it at most once. In an operation, you can choose any element and flip it: turn a $0$ into a $1$ or vice-versa.

What is the maximum number of inversions$^{\ddagger}$ the array can have after performing at most one operation?

$^\dagger$ A binary array is an array that contains only zeroes and ones.

$^\ddagger$ The number of inversions in an array is the number of pairs of indices $i,j$ such that $i \lt j$ and $a_i \gt a_j$.

给你一个长度为 $n$ 的二进制数组$^{\dagger}$。你最多可以对其执行一次操作。在一次操作中，你可以任选一个元素并将其翻转：即把 $0$ 变为 $1$，或把 $1$ 变为 $0$。

在最多执行一次操作后，该数组最多能有多少个逆序对$^{\ddagger}$？

$^\dagger$ 二进制数组是指仅包含 $0$ 和 $1$ 的数组。

$^\ddagger$ 数组中的逆序对数量，是指满足 $i \lt j$ 且 $a_i \gt a_j$ 的下标对 $(i,j)$ 的个数。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the array.

The following line contains $n$ space-separated positive integers $a_1$, $a_2$,..., $a_n$ ($0 \leq a_i \leq 1$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output a single integer — the maximum number of inversions the array can have after performing at most one operation.

对于每个测试用例，输出一个整数——在最多执行一次操作后，数组可能具有的最大逆序对数量。

For the first test case, the inversions are initially formed by the pairs of indices ($1, 2$), ($1, 4$), ($3, 4$), being a total of $3$, which already is the maximum possible.

For the second test case, the inversions are initially formed by the pairs of indices ($2, 3$), ($2, 4$), ($2, 6$), ($5, 6$), being a total of four. But, by flipping the first element, the array becomes ${1, 1, 0, 0, 1, 0}$, which has the inversions formed by the pairs of indices ($1, 3$), ($1, 4$), ($1, 6$), ($2, 3$), ($2, 4$), ($2, 6$), ($5, 6$) which total to $7$ inversions which is the maximum possible.

对于第一个测试用例，初始的逆序对由索引对 $(1, 2)$、$(1, 4)$、$(3, 4)$ 构成，共 $3$ 个，这已达到可能的最大值。

对于第二个测试用例，初始的逆序对由索引对 $(2, 3)$、$(2, 4)$、$(2, 6)$、$(5, 6)$ 构成，共 $4$ 个。但若翻转第一个元素，则数组变为 ${1, 1, 0, 0, 1, 0}$，此时逆序对由索引对 $(1, 3)$、$(1, 4)$、$(1, 6)$、$(2, 3)$、$(2, 4)$、$(2, 6)$、$(5, 6)$ 构成，总计 $7$ 个逆序对，这是可能的最大值。