分析

套路题。

注意到值域是 \(200\)。

设 \(f(i,j,0/1)\) 表示前 \(i\) 位，第 \(i\) 位放 \(j\)，大于或小于等于第 \(i-1\) 位的方案数。

可以钦定第 \(1\) 位大于第 \(0\) 位，第 \(n\) 位小于等于第 \(n-1\) 位。

转移 \[ f(i,j,0) = \sum_{k=1}^{j-1} \Big( f(i-1,k,0) + f(i-1,k,1) \Big) \] 不管 \(k\) 和 \(a_{i-2}\) 的关系如何，都一定满足条件。 \[ f(i,j,1) = \sum_{k=j}^{200} \Big( f(i-1,k,1) \Big) + f(i-1,j,0) \] 当 \(a_{i-1} = j\) 时，\(a_{i-2}\) 无论是多少都能满足条件，否则必须保证 \(a_{i-2} \ge a_{i-1}\)。

当 \(a_i \neq -1\) 的时候，只要在转移稍加限制即可。

前缀和优化一下就过了，复杂度 \(O(200n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5, mod=998244353;
int n, a[N], f[N][205][2], s[N][2];
signed main() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	if(a[1]!=-1) f[1][a[1]][0]=1, s[a[1]][0]=1;
	else for(int i=1;i<=200;++i) f[1][i][0]=1, s[i][0]=1;
	for(int i=1;i<=200;++i) s[i][0]+=s[i-1][0];
	for(int i=2;i<=n;++i) {
		if(a[i]!=-1) {
			// for(int k=1;k<a[i];++k) (f[i][a[i]][0]+=(f[i-1][k][0]+f[i-1][k][1])%mod)%=mod;
			// for(int k=a[i];k<=200;++k) (f[i][a[i]][1]+=f[i-1][k][1])%=mod;
			f[i][a[i]][0]=(s[a[i]-1][0]+s[a[i]-1][1])%mod;
			f[i][a[i]][1]=(s[200][1]-s[a[i]-1][1]+mod)%mod;
			(f[i][a[i]][1]+=f[i-1][a[i]][0])%=mod;
		}
		else {
			for(int j=1;j<=200;++j) {
				f[i][j][0]=(s[j-1][0]+s[j-1][1])%mod;
				f[i][j][1]=(s[200][1]-s[j-1][1]+mod)%mod;
				(f[i][j][1]+=f[i-1][j][0])%=mod;
				// for(int k=1;k<j;++k) {
					// (f[i][j][0]+=(f[i-1][k][0]+f[i-1][k][1])%mod)%=mod;
				// }
				// for(int k=j;k<=200;++k) {
					// (f[i][j][1]+=f[i-1][k][1])%=mod;
				// }
				// (f[i][j][1]+=f[i-1][j][0])%=mod;
			}
		}
		for(int j=1;j<=200;++j) {
			s[j][0]=(s[j-1][0]+f[i][j][0])%mod;
			s[j][1]=(s[j-1][1]+f[i][j][1])%mod;
		}
	}
	int ans=0;
	if(a[n]!=-1) ans=f[n][a[n]][1];
	else for(int i=1;i<=200;++i) (ans+=f[n][i][1])%=mod;
	printf("%lld\n",ans);
}