Increasing Subsequence

In a sequence of integers $a_1, a_2, \ldots, a_n$, if an increasing subsequence is not a subsequence of other increasing subsequences, we call it maximal. A subsequence is a sequence we can get by erasing some (possibly zero) elements from the original sequence.

Finding or counting the longest increasing subsequence is a classic problem. Now Yukikaze wants you to count the number of maximal increasing subsequences in some permutations modulo $998244353$. A permutation of length $n$ is a sequence of numbers such that every number from $1$ to $n$ appears exactly once.

The first line of the input contains a single integer $T$ $(1 \leq T \leq 10^4)$, denoting the number of test cases.

The first line of each test case contains a single integer $n$ $(1 \leq n \leq 10^5)$, denoting the length of the permutation.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le n)$, denoting the permutation. It's guaranteed that every number from $1$ to $n$ appears exactly once.

The sum of $n$ in all test case will not exceed $2 \times 10^5$.

For each test case, output a single integer denoting the number of the maximal increasing subsequences in the given permutation modulo $998244353$.

2
4
2 1 4 3
5
1 5 2 4 3

4
3

2021“MINIEYE杯”中国大学生算法设计超级联赛（4）