시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
9 초 | 768 MB | 2 | 1 | 1 | 100.000% |
A nondecreasing subsequence $(b_1, b_2, \ldots, b_k)$ of a sequence $(a_1, a_2, \ldots, a_n)$ is said to be a maximal nondecreasing subsequence of $a$ if there is no nondecreasing subsequence $(c_1, c_2, \ldots, c_l)$ of $a$ such that $b$ is a subsequence of $c$ and $k < l$.
Given the sequence $(a_1, a_2, \ldots, a_n)$, find the length of its shortest maximal nondecreasing subsequence.
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow.
The description of each test case starts with a line containing one integer $n$ ($1 \le n \le 10^6$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).
For each test case, print one integer: the length of the shortest maximal nondecreasing subsequence of the given sequence $a$.
1 5 1 2 8 4 9
4