← 返回题目列表

AtCoder · awtf2026algo_b

B. 窗口记录

中文机器翻译题面 查看原题

分数: 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