#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e6+10,mod=998244353; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,a[maxn],dp[maxn],f[maxn],g[maxn]; int mxl[maxn],mxr[maxn]; struct BIT { int t[maxn]; int lb(int x){return x&(-x);} void upd(int x,int v){x++;v%=mod;for(;x<=n+5;x+=lb(x))(t[x]+=v)%=mod;} int qry(int x){x++;if(x<0)return 0;int res=0;for(;x;x-=lb(x))(res+=t[x])%=mod;return res;} }T1,T2; void sol(int l,int r){ if(l==r){ if(!l)dp[l]=1;return; }int mid=l+r>>1; sol(l,mid); mxl[mid+1]=0; mxl[mid]=a[mid];down(i,mid-1,l+1)mxl[i]=max(mxl[i+1],a[i]); mxr[mid+1]=a[mid+1];up(i,mid+2,r)mxr[i]=max(mxr[i-1],a[i]); int pos=mid; up(i,l,mid)T1.upd(mxl[i+1]+i,dp[i]); up(i,mid+1,r){ while(pos>=l&&mxl[pos+1]<mxr[i]){ T1.upd(mxl[pos+1]+pos,mod-dp[pos]); T2.upd(pos,dp[pos]); pos--; } (dp[i]+=T1.qry(i))%=mod; (dp[i]+=T2.qry(i-mxr[i]))%=mod; } up(i,l,pos)T1.upd(mxl[i+1]+i,mod-dp[i]); up(i,pos+1,mid)T2.upd(i,mod-dp[i]); sol(mid+1,r); } void slv(){ n=read();up(i,1,n)a[i]=read(); sol(0,n); memcpy(f,dp,sizeof(f)); memset(dp,0,sizeof(dp)); reverse(a+1,a+n+1); sol(0,n); //up(i,0,n)printf("%d ",dp[i]);printf("\n"); memcpy(g,dp,sizeof(g)); reverse(g+1,g+n+1);g[n+1]=1; //up(i,0,n)printf("%d ",f[i]);printf("\n"); //up(i,1,n+1)printf("%d ",g[i]);printf("\n"); reverse(a+1,a+n+1); up(i,1,n){ int res=0,mx=1; down(j,i,1){ mx=max(mx,((j==i)?1:a[j])); int mxx=mx; up(k,i,n){ mxx=max(mxx,((k==i)?1:a[k])); if(mxx<=k-j+1)(res+=f[j-1]*1ll*g[k+1]%mod)%=mod; } }printf("%d ",res); } }int main(){ //freopen("divide.in","r",stdin); //freopen("divide.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }