Three Blocks Palindrome (easy version)
Contest: Codeforces Round 634 (Div. 3)
Difficulty rating: 1700
Tags: binary search, brute force, data structures, dp, two pointers

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]$$$.

Input format:
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$$$).

Output format:
For each test case, print the answer — the maximum possible length of some subsequence of $$$a$$$ that is a three blocks palindrome.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
7
2
4
1
1
3

Editorial:
Let's precalculate for each number $$$c$$$ ($$$0$$$-indexed) the array $$$pref_c$$$ of length $$$n+1$$$, where $$$pref_c[i]$$$ is the number of occurrences of the number $$$c$$$ on the prefix of length $$$i$$$. This can be done with easy dynamic programming (just compute prefix sums). Also let $$$sum(c, l, r)$$$ be $$$pref_c[r + 1] - pref_c[l]$$$ and it's meaning is the number of occurrences of the number $$$c$$$ on the segment $$$[l; r]$$$ ($$$0$$$-indexed).
Firstly, let's update the answer with $$$\max\limits_{c=0}^{25} pref_c[n]$$$ (we can always take all occurrences of the same element as the answer). Then let's iterate over all possible segments of the array. Let the current segment be $$$[l; r]$$$. Consider that all occurrences of the element in the middle block belong to $$$a_l, a_{l+1}, \dots, a_r$$$. Then we can just take the most frequent number on this segment ($$$cntin = \max\limits_{c=0}^{25} sum(c, l, r)$$$). We also have to choose the number for the first and the last blocks. It is obvious that for the number $$$num$$$ the maximum amount of such numbers we can take is $$$min(sum(num, 0, l - 1), sum(num, r + 1, n - 1))$$$. So $$$cntout = \max\limits_{c=0}^{25} min(sum(c, 0, l - 1), sum(c, r + 1, n - 1))$$$. And we can update the answer with $$$2cntout + cntin$$$.
Time complexity: $$$O(n^2 \cdot AL)$$$, where $$$AL$$$ is the size of alphabet (the maximum value of $$$a_i$$$).