1335E1.md (2180B)
1 Source: https://codeforces.com/problemset/problem/1335/E1 2 3 E1. Three Blocks Palindrome (easy version) 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The only difference between easy and hard versions is constraints. 22 23 You are given a sequence $a$ consisting of $n$ positive integers. 24 25 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. 26 27 Your task is to choose the maximum by length subsequence of $a$ that is a three blocks palindrome. 28 29 You have to answer $t$ independent test cases. 30 31 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]$. 32 33 Input 34 35 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. 36 37 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$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ ($\sum n \le 2000$). 40 41 Output 42 43 For each test case, print the answer — the maximum possible length of some subsequence of $a$ that is a three blocks palindrome. 44 45 Example 46 47 Input 48 49 ``` 50 6 51 8 52 1 1 2 2 3 2 1 1 53 3 54 1 3 3 55 4 56 1 10 10 1 57 1 58 26 59 2 60 2 1 61 3 62 1 1 1 63 ``` 64 65 Output 66 67 ``` 68 7 69 2 70 4 71 1 72 1 73 3 74 ```