分数: 900 点
问题陈述
给你一个长度为正整数的序列 N, A=(A_1,A_2,\ldots,A_N)。 查找、取模 998244353,长度为正整数的序列数 N, x=(x_1,x_2,\ldots,x_N),满足以下所有条件。
- x_i \leq A_i 适用于所有人 i.
- 存在一个排列 p=(p_1,p_2,\ldots,p_{2N-1}) of (1,2,\ldots,2N-1) 满足以下条件。
- 对于每个 i (1 \leq i \leq N),考虑长度序列 N, (p_i,p_{i+1},\ldots,p_{i+N-1})。正好有 x_i 该序列的“前缀最大值”的不同值。更准确地说, 索引数量 j (i \leq j \leq i+N-1)这样 p_j = \max_{i \leq k \leq j} p_k is 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).
示例输入 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