Ivan unexpectedly saw a present from one of his previous birthdays. It is array of n numbers from 1 to 200. Array is old and some numbers are hard to read. Ivan remembers that for all elements at least one of its neighbours ls not less than it, more formally:

a_{1} ≤ a_{2},

a_{n} ≤ a_{n-1} and

a_{i} ≤ max(a_{i-1},    a_{i+1}) for all i from 2 to n-1.

Ivan does not remember the array and asks to find the number of ways to restore it. Restored elements also should be integers from 1 to 200. Since the number of ways can be big, print it modulo 998244353.

Input

First line of input contains one integer n (2 ≤ n ≤ 10^{5}) — size of the array.

Second line of input contains n integers a_{i} — elements of array. Either a_{i} = -1 or 1 ≤ a_{i} ≤ 200. a_{i} = -1 means that i-th element can't be read.

Output

Print number of ways to restore the array modulo 998244353.

Examples

Input

3
1 -1 2


Output

1


Input

2
-1 -1


Output

200

Note

In the first example, only possible value of a_{2} is 2.

In the second example, a_{1} = a_{2} so there are 200 different values because all restored elements should be integers between 1 and 200.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD = 998244353
MODF = 1.0 * MOD
from math import trunc

def quickmod(a):
	return a - MODF * trunc(a / MODF)

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	(f0, f1) = ([1.0] * 201, [0.0] * 201)
	(nf0, nf1) = ([0.0] * 201, [0.0] * 201)
	for i in range(n):
		if a[i] == -1:
			for j in range(200):
				nf0[j + 1] = quickmod(nf0[j] + f0[j] + f1[j])
				nf1[j + 1] = quickmod(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
		else:
			for j in range(200):
				(nf0[j + 1], nf1[j + 1]) = (nf0[j], nf1[j])
				if j + 1 == a[i]:
					nf0[j + 1] = quickmod(nf0[j] + f0[j] + f1[j])
					nf1[j + 1] = quickmod(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
		(f0, f1, nf0, nf1) = (nf0, nf1, f0, f1)
		nf0[0] = 0.0
	os.write(1, str(int(quickmod(f1[200])) % MOD).encode())
main()


import os
from io import BytesIO
from math import trunc
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
MX = 201
MOD = 998244353
MODF = float(MOD)
quickmod = lambda x: x - MODF * trunc(x / MODF)

def main():
	n = int(input())
	a = map(int, input().split())
	dp0 = [1.0] * MX
	dp1 = [0.0] * MX
	for x in a:
		pomdp0 = [0.0] * MX
		pomdp1 = [0.0] * MX
		if x == -1:
			for val in range(1, MX):
				pomdp0[val] = quickmod(pomdp0[val - 1] + dp1[val - 1] + dp0[val - 1])
				pomdp1[val] = quickmod(pomdp1[val - 1] + dp1[MX - 1] - dp1[val - 1] + dp0[val] - dp0[val - 1])
		else:
			pomdp0[x] = quickmod(dp1[x - 1] + dp0[x - 1])
			pomdp1[x] = quickmod(dp1[MX - 1] - dp1[x - 1] + dp0[x] - dp0[x - 1])
			for val in range(x + 1, MX):
				pomdp0[val] = pomdp0[val - 1]
				pomdp1[val] = pomdp1[val - 1]
		(dp0, dp1) = (pomdp0, pomdp1)
	print(int(dp1[MX - 1] if n > 1 else dp0[MX - 1]) % MOD)
main()


from math import trunc
MX = 201
MOD = 998244353
MODF = MOD * 1.0
quickmod = lambda x: x - MODF * trunc(x / MODF)

def main():
	n = int(input())
	a = map(int, input().split())
	dp0 = [1.0] * MX
	dp1 = [0.0] * MX
	for x in a:
		pomdp0 = [0.0] * MX
		pomdp1 = [0.0] * MX
		if x == -1:
			for val in range(1, MX):
				pomdp0[val] = quickmod(pomdp0[val - 1] + dp1[val - 1] + dp0[val - 1])
				pomdp1[val] = quickmod(pomdp1[val - 1] + dp1[MX - 1] - dp1[val - 1] + dp0[val] - dp0[val - 1])
		else:
			pomdp0[x] = quickmod(dp1[x - 1] + dp0[x - 1])
			pomdp1[x] = quickmod(dp1[MX - 1] - dp1[x - 1] + dp0[x] - dp0[x - 1])
			for val in range(x + 1, MX):
				pomdp0[val] = pomdp0[val - 1]
				pomdp1[val] = pomdp1[val - 1]
		(dp0, dp1) = (pomdp0, pomdp1)
	print(int(dp1[MX - 1] if n > 1 else dp0[MX - 1]) % MOD)
main()


import os
(numb, sign) = (0, 1)
a = []
s = os.read(0, os.fstat(0).st_size)
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] == 45:
		sign = -1
	elif s[i] != 13:
		a.append(sign * numb)
		(numb, sign) = (0, 1)
if s[-1] >= 48:
	a.append(sign * numb)
MOD = 998244353
MODF = 1.0 * MOD
BIGMOD = 10 ** 4 * MODF
modder = lambda x: x if -BIGMOD < x < BIGMOD else x % MODF
mod_add = lambda x: x - MOD if x >= MOD else x
mod_sub = lambda x: x + MOD if x < 0 else x
(f0, f1) = ([1.0] * 201, [0.0] * 201)
for i in range(a[0]):
	(nf0, nf1) = ([0.0] * 201, [0.0] * 201)
	if a[i + 1] == -1:
		for j in range(200):
			nf0[j + 1] = nf0[j] + f0[j] + f1[j]
			nf1[j + 1] = nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200]
	else:
		for j in range(200):
			(nf0[j + 1], nf1[j + 1]) = (nf0[j], nf1[j])
			if j + 1 == a[i + 1]:
				nf0[j + 1] = nf0[j] + f0[j] + f1[j]
				nf1[j + 1] = nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200]
	if i % 3 == 0:
		for j in range(200):
			nf0[j + 1] %= MODF
			nf1[j + 1] %= MODF
	(f0, f1) = (nf0, nf1)
os.write(1, str(int(f1[200]) % MOD).encode())


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
dp = [[0, 0] for i in range(201)]
for i in range(201):
	dp[i][1] = 1
mod = 998244353
for i in range(1, n + 1):
	dp1 = [[0, 0] for _ in range(201)]
	for j in range(1, 201):
		if a[i - 1] == -1 or a[i - 1] == j:
			dp1[j][0] = (dp1[j][0] + dp[j - 1][1] + dp[j - 1][0]) % mod
			dp1[j][1] = (dp1[j][1] + dp[200][1] - dp[j - 1][1] + dp[j][0] - dp[j - 1][0]) % mod
		dp1[j][0] = (dp1[j][0] + dp1[j - 1][0]) % mod
		dp1[j][1] = (dp1[j][1] + dp1[j - 1][1]) % mod
	dp = dp1
print(dp[200][1])


MOD = 998244353.0
float_prec = 1801439850948198.5
float_mod = lambda x: x if -float_prec < x < float_prec else x % MOD
n = int(input())
a = [int(i) for i in input().split()]
(f0, f1) = ([1.0] * 201, [0.0] * 201)
for i in range(n):
	(nf0, nf1) = ([0.0] * 201, [0.0] * 201)
	if a[i] == -1:
		for j in range(200):
			nf0[j + 1] = float_mod(nf0[j] + f0[j] + f1[j])
			nf1[j + 1] = float_mod(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
	else:
		for j in range(200):
			(nf0[j + 1], nf1[j + 1]) = (nf0[j], nf1[j])
			if j + 1 == a[i]:
				nf0[j + 1] = float_mod(nf0[j] + f0[j] + f1[j])
				nf1[j + 1] = float_mod(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
	(f0, f1) = (nf0, nf1)
print(int(f1[200] % MOD))
jsr = 69


import os
from io import BytesIO
from math import trunc
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD = 998244353
MODF = float(MOD)
MAGIC = 6755399441055744.0
SHRT = 65536.0
MODF_INV = 1.0 / MODF
SHRT_INV = 1.0 / SHRT
fround = lambda x: x + MAGIC - MAGIC
fmod = lambda a: a - MODF * fround(MODF_INV * a)
fmul = lambda a, b: fmod(fmod(a * SHRT) * fround(SHRT_INV * b) + a * (b - SHRT * fround(b * SHRT_INV)))

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	(f0, f1) = ([1.0] * 201, [0.0] * 201)
	(nf0, nf1) = ([0.0] * 201, [0.0] * 201)
	for i in range(n):
		if a[i] == -1:
			for j in range(200):
				nf0[j + 1] = fmod(nf0[j] + f0[j] + f1[j])
				nf1[j + 1] = fmod(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
		else:
			for j in range(200):
				(nf0[j + 1], nf1[j + 1]) = (nf0[j], nf1[j])
				if j + 1 == a[i]:
					nf0[j + 1] = fmod(nf0[j] + f0[j] + f1[j])
					nf1[j + 1] = fmod(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
		(f0, f1, nf0, nf1) = (nf0, nf1, f0, f1)
		nf0[0] = 0.0
	os.write(1, str(int(fmod(f1[200])) % MOD).encode())
main()


n = int(input())
a = list(map(int, input().split()))
dp = [[0, 0] for i in range(201)]
for i in range(201):
	dp[i][1] = 1
mod = 998244353
for i in range(1, n + 1):
	dp1 = [[0, 0] for _ in range(201)]
	for j in range(1, 201):
		if a[i - 1] == -1 or a[i - 1] == j:
			dp1[j][0] = (dp1[j][0] + dp[j - 1][1] + dp[j - 1][0]) % mod
			dp1[j][1] = (dp1[j][1] + dp[200][1] - dp[j - 1][1] + dp[j][0] - dp[j - 1][0]) % mod
		dp1[j][0] = (dp1[j][0] + dp1[j - 1][0]) % mod
		dp1[j][1] = (dp1[j][1] + dp1[j - 1][1]) % mod
	dp = dp1
print(dp[200][1])


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD = 998244353
MODF = 1.0 * MOD
MODF_inv = 1.0 / MODF
SHRT = 1.0 * (1 << 16)
SHRT_inv = 1.0 / SHRT
MAGIC = float(2 ** 52 + 2 ** 51)
ffloor = lambda x: x + MAGIC - MAGIC
modder = lambda a: a - MODF * ffloor(MODF_inv * a)
mod_prod = lambda a, b: modder(modder(a * SHRT) * ffloor(SHRT_inv * b) + a * (b - SHRT * ffloor(b * SHRT_inv)))

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	(f0, f1) = ([1.0] * 201, [0.0] * 201)
	(nf0, nf1) = ([0.0] * 201, [0.0] * 201)
	for i in range(n):
		if a[i] == -1:
			for j in range(200):
				nf0[j + 1] = modder(nf0[j] + f0[j] + f1[j])
				nf1[j + 1] = modder(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
		else:
			for j in range(200):
				(nf0[j + 1], nf1[j + 1]) = (nf0[j], nf1[j])
				if j + 1 == a[i]:
					nf0[j + 1] = modder(nf0[j] + f0[j] + f1[j])
					nf1[j + 1] = modder(nf1[j] - f0[j] + f0[j + 1] - f1[j] + f1[200])
		(f0, f1, nf0, nf1) = (nf0, nf1, f0, f1)
		nf0[0] = 0.0
	os.write(1, str(int(modder(f1[200])) % MOD).encode())
main()