Stairs
Contest: Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3400
Tags: combinatorics, divide and conquer, dp, fft, math

For a permutation $$$p$$$ of numbers $$$1$$$ through $$$n$$$, we define a stair array $$$a$$$ as follows: $$$a_i$$$ is length of the longest segment of permutation which contains position $$$i$$$ and is made of consecutive values in sorted order: $$$[x, x+1, \ldots, y-1, y]$$$ or $$$[y, y-1, \ldots, x+1, x]$$$ for some $$$x \leq y$$$. For example, for permutation $$$p = [4, 1, 2, 3, 7, 6, 5]$$$ we have $$$a = [1, 3, 3, 3, 3, 3, 3]$$$.

You are given the stair array $$$a$$$. Your task is to calculate the number of permutations which have stair array equal to $$$a$$$. Since the number can be big, compute it modulo $$$998\,244\,353$$$. Note that this number can be equal to zero.

Input format:
The first line of input contains integer $$$n$$$ ($$$1 \le n \le 10^5$$$)  — the length of a stair array $$$a$$$.

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

Output format:
Print the number of permutations which have stair array equal to $$$a$$$. Since the number can be big, compute it modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 10.0 s
Memory limit: 1024.0 MB

Example input:
6
3 3 3 1 1 1

Example output:
6

Example input:
7
4 4 4 4 3 3 3

Example output:
6

Editorial:
First of all, we need to transform the stair array into some other structure. Let's show that for each number, there is only one longest stair covering it, and these longest stairs are disjoint.
Suppose that some number $$$x$$$ belongs to two different ascending stairs. We can easily expand these stairs to the left and to the right and find the longest ascending stair covering the number. So, it means that the longest ascending stair covering a number is unique. The same for descending stairs.
Now suppose that some number $$$x$$$ belongs to an ascending stair of length $$$\ge 2$$$ and a descending stair of length $$$\ge 2$$$. It is impossible because it would mean that we have consecutive values $$$[x-1, x, x-1]$$$ or $$$[x+1, x, x+1]$$$ in the permutation, but since it is a permutation, all values should be distinct. So, the longest stair covering each number is unique.
Let's split the stair array into this sequence of longest stairs. The first element of the stair array belongs to some stair. If $$$a_1 = k$$$, then the first $$$k$$$ elements form a stair. Let's check that all these $$$k$$$ elements are equal to $$$k$$$ and split them into a stair of length $$$k$$$, then continue the same algorithm from $$$a_{k+1}$$$.
Okay, now we have an array of the lengths of the longest stairs. Each stair represents some segment of numbers, and all stairs can be enumerated by the index of their value segment. So, it looks like the number of permutations that yeild this array of longest stairs is $$$s! 2^{s'}$$$, where $$$s$$$ is the number of stairs and $$$s'$$$ is the number of stairs having length $$$\ge 2$$$. The reasoning behind this formula is that each stair gets assigned an index corresponding to the index of its value segment in the sorted order, and for stairs of length $$$\ge 2$$$, we can choose whether they are ascending or descending. Is that formula right?
Unfortunately, no. The fact that we have the array of longest stairs means that we need to ensure that no pair of adjacent stairs merge. And there's no easy way to change this formula, unfortunately.
Let's use inclusion-exclusion to eliminate all "bad" permutations. We have $$$s-1$$$ constraints that shouldn't be violated:
• stairs $$$1$$$ and $$$2$$$ shouldn't merge;
• stairs $$$2$$$ and $$$3$$$ shouldn't merge;
• ...;
• stairs $$$s-1$$$ and $$$s$$$ shouldn't merge.
For every $$$i$$$ from $$$0$$$ to $$$s-1$$$, we can calculate the number of ways to choose $$$i$$$ constraints to be violated and a permutation that violates these constrains (and maybe some others), like in the usual inclusion-exclusion formula applications. These values can be calculated with the following dynamic programming: $$$dp_{n,k,t}$$$ is the number of ways to choose this set of $$$k$$$ violated constraints and a permutation for $$$n$$$ first stairs, and $$$t$$$ represents the type of the last stair (ascending/descending or having size $$$1$$$).
What are the transitions in this dynamic programming? When placing a new stair, we may choose either to explicitly violate the constraint on merging it with the previous one (so, we transition to a state $$$dp_{n+1,k+1,t'}$$$ and maybe multiply/divide the value by $$$2$$$ if we are merging two size-$$$1$$$ stairs or merging two stairs with different types). Or we can choose to just make an entirely new stair, choosing one of $$$n-k+1$$$ values for it (since we already have $$$n-k$$$ stairs), choosing its type if its length is $$$\ge 2$$$, and transitioning to $$$dp_{n+1,k,t'}$$$.
The main drawback of this solution is that it's $$$O(n^2)$$$. Let's find a way to optimize it.
Let's calculate this dynamic programming in a divide-and-conquer fashion. Let's say that for some segment $$$[l, r]$$$ of stairs, we will calculate a three-dimensional array $$$dp_{tl,tr,i}$$$ — the number of ways to violate $$$i$$$ constraints in this segment so that the leftmost stair in this segment has type $$$tl$$$, and the rightmost stair in this segment has type $$$tr$$$.
Suppose we want to merge these two segments. We either merge the leftmost stair of the right segment with the rightmost stair of the left segment, or don't. Let's analyze the case when we don't merge them. Let's analyze the value of $$$dp_{tl, tr, i}$$$ in the resulting array. Suppose we violate $$$k$$$ constraints in the left segment, this leaves us to violate $$$i-k$$$ constraints in the right segment. So, the value of $$$dp_{tl,tr,i}$$$ in the resulting merged structure will be the sum of $$$dp_{tl,?,k}$$$ from the left segment multiplied by $$$dp_{?,tr,i-k}$$$ from the right segment (where $$$?$$$ can represent any type). And if we treat the values from the left and the right segment as polynomials (where value of $$$dp_{tl,?,k}$$$ or $$$dp_{?,tr,k}$$$ is the coefficient for $$$x^k$$$), merging them is exactly polynomial multiplication! So we can use FFT so speed up the merging.
If we want to merge two segments while explicitly violating the constraint that the rightmost stair in the left segment and the leftmost stair in the right segment shouldn't be merged into one, it can be done with polynomial multiplication as well, but you also have to multiply the result by some coefficient that arises from merging those two stairs (if both of them had size $$$1$$$, then we multiply the result by $$$2$$$ since we can choose whether the resulting stair is ascending or descending; and if both of them had size $$$\ge 1$$$, we divide the result by $$$2$$$ since we cannot merge an ascending stair with a descending one).
So, this optimization allows us to merge two segments of length $$$n$$$ in time $$$O(n \log n)$$$, and as the usual FFT + D&C combination, this results in a complexity of $$$O(n \log^2 n)$$$, though with a fairly large constant factor.