给你一个二进制数组$$$^{\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$$$。
输出
对于每个测试用例,输出一个整数 - 数组在执行最多一个操作后可以拥有的最大反转次数。
示例
输入 #1
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
输出 #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$$$ 反转,这是可能的最大值。