B. Stay or Mirror

题目描述

给定一个长度为 n 的排列 p₁, p₂, …, pₙ。

你需要按照如下方式构造一个数组 a₁, a₂, …, aₙ：

• 对于每个 1 ≤ i ≤ n，选择将 aᵢ 设为 pᵢ，或者设为 2n - pᵢ。

请找出数组 a₁, a₂, …, aₙ 中可能出现的最少逆序对数量。

长度为 n 的排列是指由 n 个不同的整数组成，且这些整数均在 1 到 n 之间的数组。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是（2 出现了两次），[1,3,4] 也不是（n=3 但数组中有 4）。

数组 a₁, a₂, …, aₙ 中的逆序对是指满足 1 ≤ i < j ≤ n 且 aᵢ > aⱼ 的索引对 (i, j)。

输入格式

每个测试包含多组测试用例。第一行输入测试用例的数量 t（1 ≤ t ≤ 1e3）。 每个测试用例的第一行输入一个整数 n（2 ≤ n ≤ 5e3）。 第二行输入 n 个整数 p₁, p₂, …, pₙ（1 ≤ pᵢ ≤ n），保证这是一个排列。 保证所有测试用例的 n 之和不超过 5e3。

输出格式

对于每个测试用例，输出一个整数 —— 数组 a 中可能的最少逆序对数量。

样例输入

5
2
2 1
3
2 1 3
4
4 3 2 1
5
2 3 1 5 4
6
2 3 4 1 5 6

样例输出

0
1
0
2
2

提示

在第一个测试用例中，唯一的最优数组 a 是 [2, 3]，逆序对数量为 0。 在第二个测试用例中，一个最优数组 a 是 [2, 5, 3]，逆序对数量为 1。另一个可能的最优数组 a 是 [2, 1, 3]。