1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<bits/stdc++.h>
#define rint register int
#define uint unsigned int
using namespace std;
inline int read(){
char c=getchar();
int x=0;
while(c<48||c>57)
c=getchar();
while(c>=48&&c<=57){
x=x*10+c-48;
c=getchar();
}
return x;
}
const int N=1025;
int f[N][N][2],g[N][2],st[N][25],lg[N],n,h[N],fa[N],len[N],siz[N];
vector<int> E[N];
bool cmp(int x,int y){
if(h[x]==h[y]) return x<y;
else return h[x]<h[y];
}
int Min(int x,int y){
if(cmp(x,y)) return x;
else return y;
}
void rmq(){
int t=lg[n];
for(rint i(1);i<=t;i++){
for(rint j(1);j+(1<<i)-1<=n;j++)
st[j][i]=Min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
int ask(int l,int r){
int k=lg[r-l+1];
return Min(st[l][k],st[r-(1<<k)+1][k]);
}
int build(int l,int r) {
if(l>r)
return 0;
int mid,lc,rc;
mid=ask(l,r);
lc=build(l,mid-1);
rc=build(mid+1,r);
if(lc!=0){
fa[lc]=mid;
E[mid].push_back(lc);
}
if(rc!=0){
fa[rc]=mid;
E[mid].push_back(rc);
}
len[mid]=r-l+1;
return mid;
}
void add(int &x,int y){
x+=y-998244353;
x+=(x>>31)&998244353;
}
int qpow(int x,int y){
int ans=1;
while(y!=0){
if(y&1)
ans=1ll*ans*x%998244353;
x=1ll*x*x%998244353;
y>>=1;
}
return ans;
}
void treedp(int u){
f[u][0][1]=1;
f[u][1][1]=998244352;
f[u][1][0]=1;
int H=h[u]-h[fa[u]];
siz[u]=1;
for(auto v:E[u]){
treedp(v);
for(rint i(0);i<=siz[u];i++){
g[i][0]=f[u][i][0];
g[i][1]=f[u][i][1];
f[u][i][0]=f[u][i][1]=0;
}
for(rint i(0);i<=siz[u];i++){
for(rint j(0);j<=siz[v];j++){
add(f[u][i+j][1],1ll*g[i][1]*f[v][j][1]%998244353);
int val=1ll*(g[i][1]+g[i][0])%998244353*(f[v][j][1]+f[v][j][0])%998244353;
add(val,998244353-1ll*g[i][1]*f[v][j][1]%998244353);
add(f[u][i+j][0],val);
}
}
siz[u]+=siz[v];
}
for(rint p=0;p<=len[u];p++){
int v=qpow(2,len[u]-p);
f[u][p][1]=1ll*f[u][p][1]*qpow(v,H)%998244353;
add(v,998244353-1);
f[u][p][0]=1ll*f[u][p][0]*qpow(v,H)%998244353;
}
}
signed main(void){
n=read();
for(rint i(1);i<=n;i++)
h[i]=read();
for(rint i(1);i<=n;i++)
st[i][0]=i;
for(rint i(2);i<=n;i++)
lg[i]=lg[i>>1]+1;
rmq();
int rt=build(1,n);
treedp(rt);
int ans=0;
for(rint p=0;p<=n;p++){
add(ans,(1ll*f[rt][p][0]+f[rt][p][1])%998244353);
}
cout<<ans<<"\n";
return 0;
}
|
