[Solution] Count Partitions CodeChef Solution

Problem

An array $B$ of length $M$ consisting of only distinct elements is said to be good if the following condition holds:

• Let $i$ be the index of the maximum element of $B$.
• Then, $B[1,i]$ must be in ascending order, i.e, $B_1 \lt B_2 \lt B_3 \lt \ldots \lt B_i$.

For example, $[1, 2, 3], [1, 4, 3, 2]$ and $[1, 3, 2]$ are good arrays, while $[2, 1, 3]$ and $[3, 2, 4, 1]$ are not.

You are given a permutation $P$ of length $N$. You have to partition $P$ into some non-empty good subarrays. Note that every element of $P$ should be contained in exactly one subarray.

Find the total number of valid partitions.

Since the answer can be quite large, please print it modulo $998244353$.

Note: A permutation of length $N$ is an arrangement of the integers $\{1, 2, 3, \ldots, N\}$.

Input Format

• The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• Each test case consists of two lines of input.
  • The first line of each test case contains a single integer $N$, the length of $P$.
  • The second line contains $N$ space-separated distinct integers $P_1, P_2, P_3 , \ldots, P_N$.

Output Format

For each test case, output on a new line the number of valid partitions modulo $998244353$.