Three Blocks Palindrome (easy version)
题意翻译
现在给你一个数列,要求你从中删掉一些数,让剩下的数列满足一下条件
- 该数列长度为 $2x+y$,($x,y$可以等于 $0$)
- 该数列的前 $x$ 个数和后 $x$ 个数必须全部相同
- 该数列的中间 $y$ 个数必须全部相同
如当数列为 $1,2,1,3,1,2,1$ 时,最后的数列为 $1,1,3,1,1$或者 $3$ 都是可行的,但是 $1,1,1,1,2$ 就是不可行的
现在问你剩下的序列最长能有多少
题目描述
The only difference between easy and hard versions is constraints.
You are given a sequence $ a $ consisting of $ n $ positive integers.
Let's define a three blocks palindrome as the sequence, consisting of at most two distinct elements (let these elements are $ a $ and $ b $ , $ a $ can be equal $ b $ ) and is as follows: $ [\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}] $ . There $ x, y $ are integers greater than or equal to $ 0 $ . For example, sequences $ [] $ , $ [2] $ , $ [1, 1] $ , $ [1, 2, 1] $ , $ [1, 2, 2, 1] $ and $ [1, 1, 2, 1, 1] $ are three block palindromes but $ [1, 2, 3, 2, 1] $ , $ [1, 2, 1, 2, 1] $ and $ [1, 2] $ are not.
Your task is to choose the maximum by length subsequence of $ a $ that is a three blocks palindrome.
You have to answer $ t $ independent test cases.
Recall that the sequence $ t $ is a a subsequence of the sequence $ s $ if $ t $ can be derived from $ s $ by removing zero or more elements without changing the order of the remaining elements. For example, if $ s=[1, 2, 1, 3, 1, 2, 1] $ , then possible subsequences are: $ [1, 1, 1, 1] $ , $ [3] $ and $ [1, 2, 1, 3, 1, 2, 1] $ , but not $ [3, 2, 3] $ and $ [1, 1, 1, 1, 2] $ .
输入输出格式
输入格式
The first line of the input contains one integer $ t $ ( $ 1 \le t \le 2000 $ ) — the number of test cases. Then $ t $ test cases follow.
The first line of the test case contains one integer $ n $ ( $ 1 \le n \le 2000 $ ) — the length of $ a $ . The second line of the test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 26 $ ), where $ a_i $ is the $ i $ -th element of $ a $ . Note that the maximum value of $ a_i $ can be up to $ 26 $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ ( $ \sum n \le 2000 $ ).
输出格式
For each test case, print the answer — the maximum possible length of some subsequence of $ a $ that is a three blocks palindrome.
输入输出样例
输入样例 #1
6
8
1 1 2 2 3 2 1 1
3
1 3 3
4
1 10 10 1
1
26
2
2 1
3
1 1 1
输出样例 #1
7
2
4
1
1
3