Gregor and maximum length

Time limit: 0.3s Memory limit: 512MB Input: Output:

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 NN 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,1, \ 1, \ 2, \ 2, \ 3, \ 3, \ 1, \ 1, \ 2, \ 2, \ 3, \ 3, then applying the operation for x=1x = 1 yields 2, 2, 3, 3, 2, 2, 3, 3.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 a1,,aNa_1, \dots , a_N to be increasing if a1a2aNa_1 ≤ a_2 ≤ \dots ≤ a_N. Similarly we consider it to be decreasing if a1a2aNa_1 ≥ a_2 ≥ \dots ≥ a_N.

Task

More formally, you are given a sequence of NN 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 TT, the number of test cases. The description of the TT test cases follows. Each test case contains two lines. The first line of a test case contain NN, the length of the input sequence. The second line of a test case contains the input sequence.

Output data

You should output TT lines. Line ii should contain the answer for test case ii.

Restrictions

  • 1T20 0001 \leq T \leq 20 \ 000
  • Let N\sum N denote the sum of the values of NN for all the test cases within a particular input file. 1N200 0001 \leq \sum N \leq 200 \ 000.
  • Let VV be the biggest value in the sequence. 1V1091 \leq V \leq 10^9
# Points Restrictions
1 6 The input sequence is increasing.
2 6 The input sequence is deincreasing.
3 7 V3V \leq 3
4 19 No two elements in an input sequence are equal.
5 23 N4 000\sum N \leq 4 \ 000
6 39 No further restrictions.

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 22.

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

Log in or sign up to be able to send submissions!