G. Longest Step-function Subsequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We say that a sequence $$$x_1, x_2, \dots, x_n$$$ is a step-function if there exist two distinct numbers $$$A$$$ and $$$B$$$ and some index $$$1 \lt k \le n$$$ such that $$$x_i = A$$$ for $$$i \lt k$$$ and $$$x_i = B$$$ for $$$i \ge k$$$.

Informally, a step-function is a sequence that changes value exactly once, so that it looks like $$$[A, A, \dots, A, B, B, \dots, B]$$$.

For example, the sequences $$$[1, 1, 1, 3, 3, 3]$$$, $$$[7, 7, 7, 6]$$$, and $$$[100, 101, 101]$$$ are all step-functions, and the sequences $$$[1, 2, 3]$$$ and $$$[0, 0, 0, 0]$$$ are not.

You are given an array $$$a$$$ of length $$$n$$$. Your task is to find the length of the longest subsequence of $$$a$$$ that is a step-function. If there is no such subsequence, output $$$0$$$.

A sequence $$$x$$$ is a subsequence of another sequence $$$y$$$ if $$$x$$$ can be obtained by deleting several (possibly zero or all) elements from $$$y$$$, without changing the order of the remaining elements. For example, $$$[1, 3, 4, 7]$$$ is a subsequence of $$$[1, 2, 3, 4, 5, 6, 7, 8]$$$, and $$$[3, 3]$$$ is a subsequence of itself, but $$$[4, 3]$$$ is not a subsequence of $$$[1, 2, 3, 4]$$$.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  – the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the values in the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case output a single integer  – the length of the longest subsequence of $$$a$$$ that is a step-function, or $$$0$$$ of no such subsequence exists.

Example
Input
4
11
2 1 3 1 2 1 0 2 0 3 0
8
6 6 6 7 7 6 6 6
4
0 0 0 0
14
-3 -1 -3 -1 -3 -1 -1 -2 -1 -2 -1 -1 -1 -4
Output
6
5
0
9
Note

In the first test case, the longest step-function subsequence is $$$[1, 1, 1, 0, 0, 0]$$$.

In the second test case, the longest step-function subsequences are $$$[6, 6, 6, 7, 7]$$$ and $$$[7, 7, 6, 6, 6]$$$. The subsequence $$$[6, 6, 6, 6, 6, 6]$$$ is longer, but it is not a step-function subsequence because it does not contain two distinct values.

In the third test case, there are no step-function subsequences because there is only one distinct value in the array.