AT_awtf2026algo_b.Window Records

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$.

给你一个长度为 $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})$。该子序列中恰好有 $x_i$ 个值是“前缀最大值”。更准确地说，满足 $p_j = \max_{i \leq k \leq j} p_k$ 的下标 $j$（其中 $i \leq j \leq i+N-1$）的个数恰好为 $x_i$。

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输入从标准输入中按以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output the answer.

输出答案。

Sample 1 Explanation:
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 3 Explanation:
For example, consider $x=(3,1,3)$. No choice of $p$ satisfies the conditions.

Constraints

• $2 \leq N \leq 50$
• $1 \leq A_i \leq N$
• All input values are integers.

样例 1 解释：
例如，考虑 $x=(2,1)$。此时 $p=(2,3,1)$ 满足条件。

共有四种可能的 $x$ 值：$(1,1),(1,2),(2,1),(2,2)$。

样例 3 解释：
例如，考虑 $x=(3,1,3)$。不存在满足条件的 $p$。

限制条件

• $2 \leq N \leq 50$
• $1 \leq A_i \leq N$
• 所有输入值均为整数。