RoAlgo Contest #7 | 3secv

"And when you think that they actually made the tests for joingraf..."

Task

After conducting the tests for the joingraph problem at the last RoAlgo contest, the committee realized that a special problem was still needed. After extensive discussions, the following problem was created:

Given $t$ arrays $a$ of $n$ numbers, find the length of the longest subarray that contains at most $3$ distinct numbers. An example of such a subarray is: $9 \ 1 \ 0$.

Input data

The first line of the input contains the number $t$. For each test, the first line contains $n$, representing the number of numbers. The second line contains the $n$ numbers.

Output data

For each test, print the maximum length of a subarray with at most $3$ distinct numbers.

Constraints and clarifications

• $1 \leq t \leq 1\ 000$
• $1 \leq n \leq 10^6$
• The sum of the lengths of all $t$ arrays does not exceed $10^6$.
• $1 \leq a_i \leq 10^9$

Example

stdin

5
10
1 4 7 4 2 4 7 3 2 3 
8
1 2 4 1 5 3 1 2
10
6 8 9 1 8 5 4 6 3 2
6
1 1 1 2 2 2
12
1 5 8 3 2 5 7 4 9 5 7 4

stdout

6
4
4
6
3

Explanation

The subarray 4 7 4 2 4 7 contains $3$ distinct numbers. There is no subarray with more than $6$ numbers that meets the criteria.