队伍调整

题目描述

Y 同学作为班长，正在组织全班同学进行一次郊游。班上的 $N$ 名同学排成了一列，编号从 $1$ 到 $N$。每位同学都有一个感兴趣的话题，第 $i$ 名同学的话题用整数 $a_i$ 表示。

为了让队伍更加和谐，Y 同学希望最小化队伍的“干扰度”。队伍的干扰度定义为：队列中相邻两名同学话题相同的对数。 形式化地，干扰度 $D$ 计算如下：

其中 $[P]$ 为艾弗森括号，当条件 $P$ 成立时值为 $1$，否则为 $0$。

作为班长，Y 同学拥有调整队伍的权力。他可以进行任意次（包括 $0$ 次）如下操作：

• 选择一个下标 $i$ ($1 \le i \le N$)，交换队伍中第 $i$ 个同学和第 $N-i+1$ 个同学的位置。

换句话说，对于每一对对称的位置 $(i, N-i+1)$，Y 同学可以选择维持原状，或者将这两个位置上的同学互换。

请你帮助 Y 同学计算，在进行任意次操作后，队伍可能达到的最小干扰度是多少。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $N$，表示队伍的长度。 第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$，表示初始时每位同学感兴趣的话题。

输出格式

对于每组测试数据，输出一行一个整数，表示能够达到的最小干扰度。

样例

样例输入 #1

9
5
1 1 1 2 3
6
2 1 2 2 1 1
4
1 2 1 1
6
2 1 1 2 2 4
4
2 1 2 3
6
1 2 2 1 2 1
5
4 5 5 1 5
7
1 4 3 5 1 1 3
7
3 1 3 2 2 3 3

样例输出 #1

1
2
1
0
0
1
1
0
2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 10^4$， $2 \le N \le 10^5$， $1 \le a_i \le N$。所有测试用例中 $N$ 的总和不超过 $2 \cdot 10^5$。