#P18318. Majority Graph

Majority Graph

Majority Graph

给定长度为 NN 的数组 A1,A2,…,ANA_1,A_2,\ldots,A_N。

按照下面的规则构造一个有 NN 个顶点的无向图 GG,顶点编号为 1,…,N1,\ldots,N:对于每一对满足 1≤i<j≤N1\le i<j\le N 的下标,当且仅当子数组

A[i,j]=[Ai,Ai+1,…,Aj]A[i,j]=[A_i,A_{i+1},\ldots,A_j]

存在一个多数元素时,在顶点 i,ji,j 之间连一条边。

长度为 LL 的数组存在多数元素,指存在某个值,其出现次数严格大于 L/2L/2。

求图 GG 的连通分量数量。

输入格式

第一行包含整数 TT,表示测试用例数。

每组测试用例包含两行:

  • 第一行包含整数 NN,表示数组长度,也是图的顶点数。
  • 第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

对于每组测试用例,输出一行,包含图 GG 的连通分量数量。

数据范围

  • 1≤T≤1051\le T\le10^5;
  • 2≤N≤2⋅1062\le N\le2\cdot10^6;
  • 1≤Ai≤N1\le A_i\le N;
  • 全部测试用例的 NN 之和不超过 2⋅1062\cdot10^6。

注意,本题的 NN 上限高于通常的数组题。

样例

输入

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

输出

2
4
1
1

说明

第一组测试中,满足条件的下标对只有 (1,3)(1,3) 和 (2,4)(2,4)。子数组 [1,2,1][1,2,1] 的多数元素是1,子数组 [2,1,2][2,1,2] 的多数元素是2,因此图有2个连通分量。

第二组测试中,只有一条边 (2,4)(2,4),因此图有4个连通分量。