题目描述

给您一个长度为 $n$ 的二进制数组†，最多允许对其执行一次操作。在操作中，可以选择任意元素并翻转它：将 0 转换为 1，或将 1 转换为 0。

最多执行一次操作后，数组可以得到的最大逆序数‡？

†二进制数组是仅包含 0 和 1 的数组。

‡数组中的逆序数是指满足 $i＜j$ 且 $a_i＞a_j$ 的索引对数。

输入格式

输入由多个测试用例组成。第一行包含整数 $t(1≤t≤10^4)$ 代表测试用例数。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(1≤n≤2⋅10^5)$ 代表数组的长度。

下一行包含 $n$ 个空格分隔的正整数 $a_1,a_2,\dots a_n(0≤a_i≤1)$ 代表数组的元素。

保证所有测试用例的 $n$ 之和不超过 $2⋅10^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$ 个逆序对，这是最大可能值。