← 返回题目列表

Codeforces · 1760/E

E. 二进制反转

中文机器翻译题面 查看原题

给你一个二进制数组$$$^{\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$$$ 反转,这是可能的最大值。