# include # include # include # include # include //# include using namespace std; typedef long long ll; typedef long double ld; typedef vector vi; typedef vector> vvi; typedef vector>> vvvi; typedef vector vl; typedef vector> vvl; typedef vector>> vvvl; typedef vector vb; typedef vector> vvb; typedef vector>> vvvb; #define rep(i,n) for(int i=0;i=0;i--) #define repsr(i,m,n) for(int i=n-1;i>=m;i--) #define replr(i,n) for(ll i=n-1;i>=0;i--) #define repslr(i,m,n) for(ll i=n-1;i>=m;i--) #define sksort(x) sort(x.begin(), x.end()) #define sksortr(x) sort(x.rbegin(), x.rend()) #define disp(x) cout << x << endl #define disps(x) cout << x << " " #define dispe cout << endl #define dispv(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj]);}dispe #define dispvv(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispv(x[xqzi]);} #define dispy cout << "Yes" << endl #define dispn cout << "No" << endl #define dispyn(x) if(x)dispy;else dispn #define dispd cout << std::setprecision(20) #define inp(x) int x;cin>>x #define inpl(x) ll x;cin>>x #define inps(x) string x;cin>>x #define allv(x) (x).begin(),(x).end() #define allrv(x) (x).rbegin(),(x).rend() #define imax(x,y) x=max(x,y) #define imin(x,y) x=min(x,y) using mint = atcoder::modint998244353; struct S{ int gval; int bval; }; struct F{ int col; int ver; }; S op(S l, S r){ return S{l.gval+r.gval,l.bval+r.bval}; } S e(){ return {0,0}; } S mapping(F l, S r){ if(l.col==0) return r; else return {(r.gval+r.bval)*(l.col==1),(r.gval+r.bval)*(l.col==2)}; } F composition(F l, F r){ if(l.ver>r.ver)return l; else return r; } F id(){ return F{0,-1}; } int main(){ inp(n); vi h(n); set st; vector v(0); map mp; rep(i,n){ cin>>h[i]; st.insert(h[i]); } int x=0; int y=1; for(int i:st){ mp[i]=y; v.push_back(S{i-x,0}); x=i; y++; } atcoder::lazy_segtree seg(v); rep(i,n){ seg.apply(0,mp[h[i]],{1+(i%2==0),i}); disp(seg.all_prod().bval); } }