infO(1) Cup 2024 Mirror - Day 1 | Gregor and maximum length

Gregor lives by the saying “One for all and all for one”, so you can(’t) imagine what he has done when he received a sequence of $N$ numbers for his birthday! He created a new operation on the sequence: delete all elements of value 𝑥 and join the remaining parts. For example, if the sequence contains the integers $1, \ 1, \ 2, \ 2, \ 3, \ 3, \ 1, \ 1, \ 2, \ 2, \ 3, \ 3,$ then applying the operation for $x = 1$ yields $2, \ 2, \ 3, \ 3, \ 2, \ 2, \ 3, \ 3.$

Gregor would like you to apply this operation a number of times so that the resulting sequence has certain properties. First, the resulting sequence must be increasing, and second, among all such increasing sequences, it must have maximum length. We consider a sequence $a_1, \dots , a_N$ to be increasing if $a_1 ≤ a_2 ≤ \dots ≤ a_N$. Similarly we consider it to be decreasing if $a_1 ≥ a_2 ≥ \dots ≥ a_N$.

Task

More formally, you are given a sequence of $N$ integers. Your task is to find the maximum length of a possible increasing sequence obtained by deleting all elements of some chosen values.

Help Gregor in his journey of discovering the answer!

Input data

Each input file contains multiple test cases. The first line of the input contains the number $T$, the number of test cases. The description of the $T$ test cases follows. Each test case contains two lines. The first line of a test case contain $N$, the length of the input sequence. The second line of a test case contains the input sequence.

Output data

You should output $T$ lines. Line $i$ should contain the answer for test case $i$.

Restrictions

• $1 \leq T \leq 20 \ 000$
• Let $\sum N$ denote the sum of the values of $N$ for all the test cases within a particular input file. $1 \leq \sum N \leq 200 \ 000$.
• Let $V$ be the biggest value in the sequence. $1 \leq V \leq 10^9$

Examples

stdin

3
2
1 1
4
1 2 1 2
10
1 2 1 2 1 3 1 2 4 3

stdout

2
2
5

Notes

In the first test case, Gregor can keep all the values, as the sequence is already increasing.

In the second test case, Gregor needs to delete at leas one of the values to get an increasing sequnce, so the answer is $2$.

In the third test case, it can be proven that by deleting values $2$ and $3$, Gregor will achieve a maximum length increasing sequence.