题目描述

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

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

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

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

输入格式

输入包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。接下来的每组测试用例描述如下。

每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$）——数组的长度。

接下来一行包含 $n$ 个用空格分隔的正整数 $a_1, a_2, \ldots, 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)$ 组成，共 $4$ 个。但如果将第一个元素翻转，数组变为 $[1, 1, 0, 0, 1, 0]$，此时逆序对由下标对 $(1, 3)$、$(1, 4)$、$(1, 6)$、$(2, 3)$、$(2, 4)$、$(2, 6)$、$(5, 6)$ 组成，共 $7$ 个，这是可能的最大值。

由 ChatGPT 4.1 翻译

来源

Codeforces 1760E，英文题名 Binary Inversions。