← 返回题目列表

AtCoder · arc146_e

E. 简单速度

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

分数: 800 点

问题陈述

给你一系列 N 正整数: A=(A_1,A_2,\dots,A_N).

有多少个整数序列 B 由之间的整数组成 1 和 N (含)满足以下所有条件?打印计数模数 998244353.

  • 对于每个整数 i 这样 1 \le i \le N,正好有 A_i 出现 i in B.
  • 对于每个整数 i 这样 1 \le i \le |B|-1,它认为 |B_i - B_{i+1}|=1.

约束

  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

3
2 3 1

示例输出 1

6

B 可以是以下六个序列。

  • (1,2,1,2,3,2)
  • (1,2,3,2,1,2)
  • (2,1,2,1,2,3)
  • (2,1,2,3,2,1)
  • (2,3,2,1,2,1)
  • (3,2,1,2,1,2)

因此,答案是 6.


示例输入 2

1
200000

示例输出 2

0

可能没有满足条件的序列。


示例输入 3

6
12100 31602 41387 41498 31863 12250

示例输出 3

750337372