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