解题思路

• 核心判定：对子数组而言，若“出现次数最多的次数”只由某一个元素达到，则该子数组存在“唯一众数”。

• 算法：双重枚举子数组的左右端点（固定左端点，向右扩展），在扩展过程中用哈希表维护：

  • freq[x]：当前子数组内元素 x 的出现次数；
  • maxFreq：当前子数组内的最高出现次数；
  • cntMax：达到 maxFreq 的元素个数。

• 增量更新：每次把右端点元素 x 加入：

题目内容

给定一个长度为$n$的整数序列$a_1,a_2,...,a_n$。我们称一个非空连续子数组$a_l,a_{l+1},...,a_r$,存在“唯一众数”，当且仅当在该子数组中，出现次数最多的数恰好只有一个(即最高频次仅由某一个数独占)。

请你求出存在唯一众数的最长子数组的长度。若不存在这样的子数组，则输出0。

名词解释:

子数组:指原序列中一段连续的元素$a_l, a_{l+1},...,a_r(1≤l≤r≤n)$。

唯一众数：在一个集合或序列中，出现次数最多的元素。若这一“最多次数”由多个不同元素同时达到，则不存在“唯一众数"。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≤T≦10^3)$代表数据组数，每组测试数据描述如下:

第一行输入一个整数$n(1≦n≦2×10^3)$;

第二行输入$n$个整数$a_1,a_2,...，a_n(|a_i|≦10^9)$

保证所有测试中$n$的总和不超过$2×10^3$。

输出描述

对于每组测试数据，输出一行一个整数，表示存在唯一众数的最长子数组长度;若不存在，输出$0$

样例1

输入

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

输出

4
3
3

说明

样例一:整个数组的最高频次由$2$和$3$同时达到，不是唯众数;但子数组$[1,2,2,3]$中2的频次为$2$且独占最高频，长度为$4$，为最优。

样例二:$[7,7,7]$的众数为7且唯一，答案为$3$。

样例三:$[1,1,2]$或$[1,2,2]$的众数分别为$1$或$2$，且均唯一，最长长度为$3$。