Successor Swap - Repovive Standard Round 6 | Repovive

18D. Successor Swap

2000 pts2s256 MB

You are given a permutation $p$ of the integers from $1$ to $n$ .

In one operation, you may do the following:

choose an index $i$ such that $i < p_i$ ;
set $j = p_i$ ;
swap the elements at indices $i$ and $j$ . In other words, swap $p_i$ and $p_j$ .

Find the number of distinct permutations that can be reached after performing any number of operations, possibly zero.

Print the answer modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$p$ is a permutation of the integers from $1$ to $n$

Input

t

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

Output

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

Samples

Input

Case 1

4
1 2 3 4

Case 2

4
2 3 4 1

Case 3

4
4 3 1 2

Explanation

Case 1

No operation can be performed, so the only reachable permutation is $(1,2,3,4)$ .

Case 2

Starting from $(2,3,4,1)$ , the following sequences of chosen indices produce all reachable permutations:

no operations: $(2,3,4,1)$
$1$ : $(3,2,4,1)$
$2$ : $(2,4,3,1)$
$3$ : $(2,3,1,4)$
$1,1$ : $(4,2,3,1)$
$1,3$ : $(3,2,1,4)$
$2,2$ : $(2,1,3,4)$
$1,1,1$ : $(1,2,3,4)$

Therefore, the answer is $8$ .

Case 3

Starting from $(4,3,1,2)$ , choosing the indices

none,
$1$ ,
$2$ ,
$1,1$ ,
$1,2$ ,
$1,1,1$

produces the six distinct reachable permutations. Therefore, the answer is $6$ .

Output

Case 1

Case 2

Case 3

Input

Case 1

8
2 3 1 5 4 8 6 7

Case 2

10
10 9 8 6 7 1 4 2 5 3

Explanation

Case 1

For example, choosing the indices $1,1,4,6,6$ produces $(1,2,3,4,5,6,7,8)$ . Considering all legal sequences gives $24$ distinct reachable permutations.

Case 2

For example, applying the operation at index $1$ nine times produces $(1,2,3,4,5,6,7,8,9,10)$ . Considering all legal sequences gives $98$ distinct reachable permutations.

Output

Case 1

Case 2

You are given a permutation $p$ of the integers from $1$ to $n$ .

In one operation, you may do the following:

choose an index $i$ such that $i < p_i$ ;
set $j = p_i$ ;
swap the elements at indices $i$ and $j$ . In other words, swap $p_i$ and $p_j$ .

Find the number of distinct permutations that can be reached after performing any number of operations, possibly zero.

Print the answer modulo $998244353$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
$p$ is a permutation of the integers from $1$ to $n$

t

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

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

No operation can be performed, so the only reachable permutation is $(1,2,3,4)$ .

Starting from $(2,3,4,1)$ , the following sequences of chosen indices produce all reachable permutations:

no operations: $(2,3,4,1)$
$1$ : $(3,2,4,1)$
$2$ : $(2,4,3,1)$
$3$ : $(2,3,1,4)$
$1,1$ : $(4,2,3,1)$
$1,3$ : $(3,2,1,4)$
$2,2$ : $(2,1,3,4)$
$1,1,1$ : $(1,2,3,4)$

Therefore, the answer is $8$ .

Starting from $(4,3,1,2)$ , choosing the indices

none,
$1$ ,
$2$ ,
$1,1$ ,
$1,2$ ,
$1,1,1$

produces the six distinct reachable permutations. Therefore, the answer is $6$ .

For example, choosing the indices $1,1,4,6,6$ produces $(1,2,3,4,5,6,7,8)$ . Considering all legal sequences gives $24$ distinct reachable permutations.

For example, applying the operation at index $1$ nine times produces $(1,2,3,4,5,6,7,8,9,10)$ . Considering all legal sequences gives $98$ distinct reachable permutations.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

18D. Successor Swap

Constraints

Input

Output

Samples

18D. Successor Swap

Constraints

Input

Output

Samples