← 返回题目列表

Codeforces · 1067/A

A. 没有局部最大值的数组

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

Ivan 意外地看到了他之前生日时收到的一份礼物。它是从 $$$1$$$ 到 $$$200$$$ 的 $$$n$$$ 数字数组。数组很旧,有些数字很难读取。 Ivan 记得对于所有元素来说,至少有一个邻居不小于它,更正式地说:

$$$a_{1} \le a_{2}$$$,

$$$a_{n} \le a_{n-1}$$$ 和

$$$a_{i} \le max(a_{i-1}, \,\, a_{i+1})$$$ 对于从 $$$2$$$ 到 $$$n-1$$$ 的所有 $$$i$$$。

Ivan不记得该数组并要求找到恢复它的方法数。恢复的元素也应该是从 $$$1$$$ 到 $$$200$$$ 的整数。由于路的数量可能很大,因此将其模 $$$998244353$$$ 打印出来。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^{5}$$$) — 数组的大小。

输入的第二行包含 $$$n$$$ 整数 $$$a_{i}$$$ — 数组元素。 $$$a_{i} = -1$$$ 或 $$$1 \le a_{i} \le 200$$$。 $$$a_{i} = -1$$$ 表示无法读取第 $$$i$$$ 个元素。

输出

打印以 $$$998244353$$$ 为模恢复数组的方法数。

示例

输入 #1

3
1 -1 2

输出 #1

1

输入 #2

2
-1 -1

输出 #2

200

注意

在第一个示例中,$$$a_{2}$$$ 的唯一可能值为 $$$2$$$。

在第二个示例中,$$$a_{1} = a_{2}$$$ 因此存在 $$$200$$$ 不同的值,因为所有恢复的元素应为 $$$1$$$ 和 $$$200$$$ 之间的整数。