Array Collapse
Contest: Educational Codeforces Round 160 (Rated for Div. 2)
Difficulty rating: 2100
Tags: data structures, divide and conquer, dp, trees

You are given an array $$$[p_1, p_2, \dots, p_n]$$$, where all elements are distinct.

You can perform several (possibly zero) operations with it. In one operation, you can choose a contiguous subsegment of $$$p$$$ and remove all elements from that subsegment, except for the minimum element on that subsegment. For example, if $$$p = [3, 1, 4, 7, 5, 2, 6]$$$ and you choose the subsegment from the $$$3$$$-rd element to the $$$6$$$-th element, the resulting array is $$$[3, 1, 2, 6]$$$.

An array $$$a$$$ is called reachable if it can be obtained from $$$p$$$ using several (maybe zero) aforementioned operations. Calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print one integer — the number of reachable arrays, taken modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
2
2 1
4
2 4 1 3
5
10 2 6 3 4

Example output:
2
6
12

Editorial:
Let's rephrase the problem a bit. Instead of counting the number of arrays, let's count the number of subsequences of elements that can remain at the end.
One of the classic methods for counting subsequences is dynamic programming of the following kind: $$$\mathit{dp}_i$$$ is the number of subsequences such that the last taken element is at position $$$i$$$. Counting exactly this is that simple. It happens that element $$$i$$$ cannot be the last overall because it is impossible to remove everything after it. Thus, let's say it a little differently: the number of good subsequences on a prefix of length $$$i$$$. Now we are not concerned with what comes after $$$i$$$ — after the prefix.
If we learned to calculate such dp, we could get the answer from it. We just need to understand when we can remove all elements after a fixed one. It is easy to see that it is enough for all these elements to be smaller than the fixed one. Then they can be removed one by one from left to right. If there is at least one larger element, then the maximum of such elements cannot be removed.
Therefore, the answer is equal to the sum of dp for all $$$i$$$ such that $$$a_i$$$ is the largest element on a suffix of length $$$n - i + 1$$$.
How to calculate such dp?
Let's look at the nearest element to the left that is larger than $$$a_i$$$. Let its position be $$$j$$$. Then any subsequence that ended with an element between $$$j$$$ and $$$i$$$ can have the element $$$i$$$ appended to it. It is only necessary to remove the elements standing before $$$i$$$. This can also be done one by one.
Can $$$j$$$ be removed as well? It can, but it's not that simple. Only the element that is the nearest larger one to the left for $$$a_j$$$ or someone else even more to the left can do this. Let $$$f[i]$$$ be the position of the nearest larger element to the left. Then the element $$$i$$$ can also extend subsequences ending in $$$a[f[i]], a[f[f[i]]], a[f[f[f[i]]]], \dots$$$.
If there are no larger elements to the left of the element — the element is the maximum on the prefix — then $$$1$$$ is added to its $$$\mathit{dp}$$$ value. This is a subsequence consisting of only this element.
The position of the nearest larger element to the left can be found using a monotonic stack: keep a stack of elements; while the element at the top is smaller, remove it; then add the current one to the stack.
Counting the dp currently works in $$$O(n^2)$$$ in the worst case. How to optimize this? The first type of transitions is optimized by prefix sums, as it is simply the sum of dp on a segment. For the second type of transitions, you can maintain the sum of dp on a chain of jumps to the nearest larger element: $$$\mathit{dpsum}_i = \mathit{dpsum}_{f[i]} + \mathit{dp}_i$$$. Now, both transitions can be done in $$$O(1)$$$.
Overall complexity: $$$O(n)$$$ for each testcase.