LaIS
Contest: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Difficulty rating: 2200
Tags: 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.

Input format:
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$$$.

Output format:
For each test case, print one integer — the length of the longest almost increasing subsequence.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
3
8
1 2 7 3 2 1 2 3
2
2 1
7
4 1 5 2 6 3 7

Example output:
6
2
7

Editorial:
Let's add $$$0$$$ to the beginning of $$$a$$$, then we'll increase LaIS by one and so it will always start from $$$0$$$. Let's look at any almost increasing subsequence (aIS) and underline elements, which are minimums in at least one consecutive pair, for example, $$$[\underline{0}, \underline{1}, \underline{2}, 7, \underline{2}, \underline{2}, 3]$$$.
Note that underlined elements form increasing subsequence (IS) and there is no more than one element between each consecutive pair. What constraints these elements have? Obviously, $$$a[pos_{i - 1}] \le a[pos_i] \ge a[pos_{i + 1}]$$$, but we can ease the constraints just to $$$a[pos_{i - 1}] \le a[pos_i]$$$, i. e. we can allow $$$a[pos_i] < a[pos_{i + 1}]$$$, since aIS will still be aIS.
Now, note that between $$$pos_{i-1}$$$ and $$$pos_{i + 1}$$$ we can choose any $$$j$$$ such that $$$a[pos_{i - 1}] \le a[j]$$$, so we can always choose the first such $$$j$$$, moreover we can precalculate such $$$j$$$ as $$$nxt_i$$$ for each $$$a_i$$$. Using stacks or something similar.
Now, we can note that each $$$a_i$$$ is either minimum in LaIS or $$$i = nxt_j$$$ for some other element $$$a_j$$$. And we can write the following dynamic programming: let $$$d[i]$$$ be the LaIS which finish in $$$a_i$$$ and it's the last minimum (we can think that the last element of LaIS is minimum in the imaginary pair). To calculate it, we can iterate $$$i$$$ from left to right and store for each value $$$x$$$ the length of LaIS with the last minimum (not the last element) equal to $$$x$$$ in Segment Tree (ST).
So, $$$d_i$$$ is equal to "get maximum over segment $$$[0, a_i]$$$ in ST" plus $$$1$$$. And we update ST in two moments: firstly, right now with value $$$d_i$$$ in position $$$a_i$$$ and secondly, after we meet the element $$$nxt_i$$$ with value $$$d_i + 1$$$ also in position $$$a_i$$$.
After we process all $$$i$$$ we'll get ST where for each $$$x$$$ the length of LaIS with last minimum equal to $$$x$$$ will be stored and the answer will be equal just to "maximum over all tree (segment $$$[0, n]$$$)".
In total, we should calculate $$$nxt_i$$$ for each $$$a_i$$$ (we can do it in linear time using stack) and maintain Segment Tree with two basic operations: range maximum and update in position. The time complexity is $$$O(n \log(n))$$$ and the space complexity is $$$O(n)$$$.