#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],pre[maxn],nxt[maxn],pre2[maxn],nxt2[maxn],stk[maxn],tp; int sf[maxn],sg[maxn]; int mxl[maxn],mxr[maxn]; int res[maxn]; struct st { int t[maxn][20],Log_2[maxn]; void init(){ up(i,2,n)Log_2[i]=Log_2[i>>1]+1; up(i,1,n)t[i][0]=a[i]; up(i,1,Log_2[n])up(j,1,n-(1<<i)+1)t[j][i]=max(t[j][i-1],t[j+(1<<i-1)][i-1]); }int qry(int l,int r){ if(l>r)return -1e9; int k=Log_2[r-l+1]; return max(t[l][k],t[r-(1<<k)+1][k]); } }st; int gpre(int p,int x){ if(st.qry(1,p)<x)return 0; //cout<<"gpre "<<p<<" "<<x<<endl; int l=1,r=p+1; while(l+1<r){ int mid=l+r>>1; if(st.qry(mid,p)<x)r=mid; else l=mid; }return l; } int gnxt(int p,int x){ if(st.qry(p,n)<=x)return n+1; int l=p-1,r=n; while(l+1<r){ int mid=l+r>>1; if(st.qry(p,mid)<=x)l=mid; else r=mid; }return r; } 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"); up(i,0,n+1){ if(!i)sf[i]=f[i],sg[i]=g[i]; else sf[i]=(sf[i-1]+f[i])%mod,sg[i]=(sg[i-1]+g[i])%mod; } reverse(a+1,a+n+1); st.init(); up(i,1,n){ while(tp&&a[stk[tp]]<a[i])tp--; pre[i]=stk[tp];stk[++tp]=i; }tp=0;stk[tp]=n+1; down(i,n,1){ while(tp&&a[stk[tp]]<=a[i])tp--; nxt[i]=stk[tp];stk[++tp]=i; }up(i,1,n)pre2[i]=gpre(pre[i]-1,a[i]),nxt2[i]=gnxt(nxt[i]+1,a[i]); //up(i,1,n)printf("%d pre:%d pre2:%d nxt:%d nxt2:%d\n",i,pre[i],pre2[i],nxt[i],nxt2[i]); up(i,1,n)res[i]=f[n]; up(i,1,n){ auto calc=[](int l1,int r1,int l2,int r2,int lim){ //cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<lim<<endl;; int res=0; if(r1-l1+1<=r2-l2+1){ up(i,l1,r1){ int pos=max(l2,i+lim-1); if(pos<=r2)(res+=f[i-1]*1ll*(sg[r2+1]-sg[pos]+mod)%mod)%=mod; } }else { up(i,l2,r2){ int pos=min(i-lim+1,r1); if(pos>=l1)(res+=g[i+1]*1ll*(sf[pos-1]-((l1>=2)?sf[l1-2]:0)+mod)%mod)%=mod; } } //cout<<"res : "<<res<<endl; return res; }; if(pre[i]){ (res[pre[i]]+=calc(pre2[i]+1,pre[i],i,nxt[i]-1,a[i]))%=mod; res[pre[i]]=(res[pre[i]]+mod-calc(pre2[i]+1,pre[i],i,nxt[i]-1,a[pre[i]]))%mod; } if(nxt[i]!=n+1){ (res[nxt[i]]+=calc(pre[i]+1,i,nxt[i],nxt2[i]-1,a[i]))%=mod; res[nxt[i]]=(res[nxt[i]]+mod-calc(pre[i]+1,i,nxt[i],nxt2[i]-1,a[nxt[i]]))%mod; } } up(i,1,n)if(a[i]!=1)(res[i]+=f[i-1]*1ll*g[i+1]%mod)%=mod; up(i,1,n)printf("%d ",res[i]);printf("\n"); }int main(){ //freopen("divide.in","r",stdin); //freopen("divide.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }