Counting Randomized Permutation Generation Methods

In this problem, we are given an integer N and a permutation P of the set {1, 2, …, N}. The permutation is assumed to be produced by the following recursive randomized algorithm:

// rand_int(l, r) returns a uniformly random integer from the interval [l, r]
vector ans;

void solve(int l, int r) {
    if (l == r) {
        ans.push_back(r);
        return;
    }
    int m = rand_int(l, r - 1);
    if (rand_int(0, 1) == 0) {
        solve(l, m);
        solve(m + 1, r);
    } else {
        solve(m + 1, r);
        solve(l, m);
    }
}

Initially, ans is empty; after calling solve(1, N), ans stores a permutation of {1, 2, …, N}. Two methods are considered different if during some call the rand_int function returns a different number. Your task is to compute, for a given permutation P, how many different sequences of random choices (i.e. different random generation methods) could produce exactly the permutation P.

The recurrence behind the algorithm is as follows. For an interval [l,r] (with r>l) the algorithm chooses an integer m in the range l ≤ m < r. This induces a partition of the set {l, l+1, …, r} into two consecutive intervals: [l, m] and [m+1, r]. Then, the outputs of the two recursive calls are concatenated in either order based on a coin toss. Hence, if we denote by f(l, r, s) the number of ways to generate a permutation from the consecutive set {s, s+1, …, s+len-1} (with len = r-l+1) then we have:

$$\text{f}(i,j,s)=\begin{cases} 1 & \text{if } i=j \text{ and } P[i]=s,\\[6pt] \displaystyle \sum_{k=1}^{\text{len}-1}\Bigl( f(i,i+k-1,s)\cdot f(i+k,j,s+k) + f(i,i+\text{len}-k-1,s+k)\cdot f(i+\text{len}-k,j,s) \Bigr) & \text{if } \min(P[i\ldots j])=s \text{ and } \max(P[i\ldots j])=s+\text{len}-1,\\[6pt] 0 & \text{otherwise.} \end{cases} $$

Your final answer should be computed modulo 998244353.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 100, for instance).

The second line contains N space‐separated integers which form a permutation of {1, 2, …, N}.

outputFormat

Output a single integer — the number of different random generation methods producing the given permutation P, taken modulo 998244353.

sample

1
1

1

</p>