I. Stairs
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.
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\)).
Print the number of permutations which have stair array equal to \(a\). Since the number can be big, compute it modulo \(998\,244\,353\).