#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/5/problems/D

Repovive

Remove Mountain - Repovive Standard Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

5D. Remove Mountain

2000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

You are given a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ .

In one operation, you can choose an index $i$ such that $1 < i < |p|$ (where $|p|$ is the current length of the permutation), $p_i > p_{i-1}$ and $p_i > p_{i+1}$ , and remove $p_i$ from the sequence. After removing $p_i$ , the remaining elements are concatenated without changing their relative order.

Find the number of different subsets of numbers that can remain after applying this operation any number of times (possibly zero). Since the answer can be very large, print it modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \ldots \quad p_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Samples

Input

Case 1

4
1 3 2 4

Case 2

5
5 3 4 2 1

Case 3

5
1 4 5 2 3

Explanation

Case 1

The initial permutation is 1 3 2 4. We can either do no operations and keep 1 3 2 4, or we can choose the element 3 (since 3 > 1 and 3 > 2) and remove it, resulting in 1 2 4. No further operations are possible. So there are 2 valid subsets.

Case 2

The sequence is 5 3 4 2 1. We can remove 4 (since 4 > 3 and 4 > 2), resulting in 5 3 2 1. We cannot remove any other elements. So the valid subsets are 5 3 4 2 1 and 5 3 2 1.

Case 3

The sequence is 1 4 5 2 3. The valid subsets are:

1 4 5 2 3 (0 operations)
1 4 2 3 (removing 5)
1 2 3 (removing 5, then removing 4 from the remaining sequence) Total 3 valid subsets.

Output

Case 1

Case 2

Case 3

You are given a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ .

Find the number of different subsets of numbers that can remain after applying this operation any number of times (possibly zero). Since the answer can be very large, print it modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \ldots \quad p_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t