/ 
Time Limit: 2 sec / Memory Limit: 2048 MiB
配点 : 900 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます． 以下の条件をすべて満たす長さ N の正整数列 x=(x_1,x_2,\ldots,x_N) の個数を 998244353 で割った余りを求めてください．
- すべての i に対し x_i \leq A_i が成り立つ．
- ある (1,2,\ldots,2N-1) の順列 p=(p_1,p_2,\ldots,p_{2N-1}) が存在し，以下の条件を満たす．
- 各 i (1 \leq i \leq N) に対し，長さ N の数列 (p_i,p_{i+1},\ldots,p_{i+N-1}) を考える．この列の prefix max の種類数がちょうど x_i である．より正確に言えば， p_j = \max_{i \leq k \leq j} p_k となる j (i \leq j \leq i+N-1) の個数が x_i である．
制約
- 2 \leq N \leq 50
- 1 \leq A_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \ldots A_N
出力
答えを出力せよ．
入力例 1
2 2 2
出力例 1
4
例えば x=(2,1) について考えると，p=(2,3,1) によって条件が満たされます．
x としてあり得るのは，(1,1),(1,2),(2,1),(2,2) の 4 通りです．
入力例 2
2 1 2
出力例 2
2
入力例 3
3 3 3 3
出力例 3
20
例えば x=(3,1,3) について考えると，どんな p を選んでも条件を満たしません．
入力例 4
4 3 2 4 3
出力例 4
44
入力例 5
10 8 3 8 10 1 5 3 1 6 4
出力例 5
2590
入力例 6
50 29 43 38 17 46 49 39 39 48 27 35 46 50 25 47 38 25 38 32 22 50 42 47 37 26 50 37 30 44 49 22 38 35 44 50 44 46 46 41 48 32 15 6 32 49 37 38 45 33 31
出力例 6
969185665
Score : 900 points
Problem Statement
You are given a sequence of positive integers of length N, A=(A_1,A_2,\ldots,A_N). Find, modulo 998244353, the number of sequences of positive integers of length N, x=(x_1,x_2,\ldots,x_N), satisfying all of the following conditions.
- x_i \leq A_i holds for all i.
- There exists a permutation p=(p_1,p_2,\ldots,p_{2N-1}) of (1,2,\ldots,2N-1) satisfying the following condition.
- For each i (1 \leq i \leq N), consider the sequence of length N, (p_i,p_{i+1},\ldots,p_{i+N-1}). There are exactly x_i different values that are "prefix max" of this sequence. More precisely, the number of indices j (i \leq j \leq i+N-1) such that p_j = \max_{i \leq k \leq j} p_k is x_i.
Constraints
- 2 \leq N \leq 50
- 1 \leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
2 2 2
Sample Output 1
4
For example, consider x=(2,1). The condition is satisfied by p=(2,3,1).
There are four possible values of x: (1,1),(1,2),(2,1),(2,2).
Sample Input 2
2 1 2
Sample Output 2
2
Sample Input 3
3 3 3 3
Sample Output 3
20
For example, consider x=(3,1,3). No choice of p satisfies the conditions.
Sample Input 4
4 3 2 4 3
Sample Output 4
44
Sample Input 5
10 8 3 8 10 1 5 3 1 6 4
Sample Output 5
2590
Sample Input 6
50 29 43 38 17 46 49 39 39 48 27 35 46 50 25 47 38 25 38 32 22 50 42 47 37 26 50 37 30 44 49 22 38 35 44 50 44 46 46 41 48 32 15 6 32 49 37 38 45 33 31
Sample Output 6
969185665