A. LaIS
data structures; dp; greedy
Let's call a sequence \(b_1, b_2, b_3 \dots, b_{k - 1}, b_k\) almost increasing if $$$\(\min(b_1, b_2) \le \min(b_2, b_3) \le \dots \le \min(b_{k - 1}, b_k).\)\( In particular, any sequence with no more than two elements is almost increasing.You are given a sequence of integers \)a_1, a_2, \dots, a_n\(. Calculate the length of its longest almost increasing subsequence.You'll be given \)t$$$ test cases. Solve each test case independently.Reminder: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
The first line contains a single integer \(t\) (\(1 \le t \le 1000\)) — the number of independent test cases.The first line of each test case contains a single integer \(n\) (\(2 \le n \le 5 \cdot 10^5\)) — the length of the sequence \(a\).The second line of each test case contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)) — the sequence itself.It's guaranteed that the total sum of \(n\) over all test cases doesn't exceed \(5 \cdot 10^5\).
For each test case, print one integer — the length of the longest almost increasing subsequence.
In the first test case, one of the optimal answers is subsequence \(1, 2, 7, 2, 2, 3\).In the second and third test cases, the whole sequence \(a\) is already almost increasing.