Palindromic Doubles
Contest: Kotlin Heroes: Episode 6
Difficulty rating: 2200
Tags: *special, data structures, dp

A subsequence is a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements.

A palindromic sequence is a sequence that is equal to the reverse of itself.

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. Any integer value appears in $$$a$$$ no more than twice.

What is the length of the longest palindromic subsequence of sequence $$$a$$$?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Then the descriptions of $$$t$$$ testcases follow.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 250\,000$$$) — the number of elements in the sequence.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Any integer value appears in $$$a$$$ no more than twice. The sum of $$$n$$$ over all testcases doesn't exceed $$$250\,000$$$.

Output format:
For each testcase print a single integer — the length of the longest palindromic subsequence of sequence $$$a$$$.

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

Note:
Here are the longest palindromic subsequences for the example testcases:

- 2 1 3 1 5 2
- 1 3 3 4 4 1 or 1 3 3 4 4 1
- 1
- 1 1
- 4 4 2 5 7 2 3 or 4 4 2 5 7 2 3

Example input:
5
6
2 1 3 1 5 2
6
1 3 3 4 4 1
1
1
2
1 1
7
4 4 2 5 7 2 3

Example output:
5
4
1
2
3

Editorial:
Let's first ignore the palindromic subsequences with the odd length. Now there are only even length palindromes.
You can observe that every value that appears in any of them, appears twice. Coincidentally, every value can appear no more than twice in the original sequence.
Let's renumerate all the values in the order of their first appearance. That way, every palindromic subsequence will actually be increasing until the middle and then decreasing. Moreover, if you take any decreasing subset of the second occurrences of the values, then the corresponding first occurrences will always be increasing. Thus, the problem turns into finding the longest decreasing subsequence of the second occurrences.
You can solve it with any algorithm you like.
Let's now observe what's the difference between the odd and the even palindromes. The only value that can be taken only once is in the middle. It doesn't really matter what is that value, so if the middle value in an even palindrome has something between its occurrences, then you can take this something as the middle element of an odd palindrome. We can also say that not only the middle value but all values of an even palindrome should have something between their occurrences — that statement is as correct.
Thus, let's solve the task twice. The first time we consider the second occurrences of all values that appears exactly twice in the sequence. The second time we only consider the second occurrences of such values that appears twice and also have their occurrences not adjacent to each other. The first answer doubled is the maximum length even palindrome. The second answer doubled and increased by one is the maximum length odd palindrome.
Overall complexity: $$$O(n \log n)$$$ per testcase.