← 返回题目列表

AtCoder · arc169_c

C. 不那么连续

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

分数: 600 点

问题陈述

给你一个整数 N。 整数序列 x=(x_1,x_2,\cdots,x_N) 长度 N 被称为 好 序列当且仅当满足以下条件时:

  • 每个元素 x 是介于 1 和 N,包括在内。
  • 对于每个整数 i (1 \leq i \leq N), 中没有位置 出现 x 其中 i 出现 i+1 或连续多次。

给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N。 的每个元素 A is -1 或之间的整数 1 和 N。 求模数 998244353,可以通过替换每个来获得好的序列 -1 in A 之间的整数 1 和 N.

约束

  • 1 \leq N \leq 5000
  • A_i=-1 or 1 \leq A_i \leq N.
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \cdots A_N

输出

打印答案。


示例输入 1

2
-1 -1

示例输出 1

3

您可以通过替换每个序列来获得四个序列 -1 之间的整数 1 和 2.

A=(1,1) 不是一个好的序列,因为 1 连续出现两次。

其他序列 A=(1,2),(2,1),(2,2) 都很好。

因此,答案是 3.


示例输入 2

3
2 -1 2

示例输出 2

2

示例输入 3

4
-1 1 1 -1

示例输出 3

0

示例输入 4

20
9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1

示例输出 4

128282166