#include #include using namespace std; //入力が必ず-mod<=a //mod<2^30. struct modint{ //mod変更が不可能. public: long long v; static void setmod(int m){} //飾り. static constexpr long long getmod(){return mod;} modint():v(0){} template modint(T a):v(a){if(v < 0) v += mod;} long long val()const{return v;} modint &operator=(const modint &b) = default; modint &operator+()const{return (*this);} modint operator-()const{return modint(0)-(*this);} modint operator+(const modint b)const{return modint(v)+=b;} modint operator-(const modint b)const{return modint(v)-=b;} modint operator*(const modint b)const{return modint(v)*=b;} modint operator/(const modint b)const{return modint(v)/=b;} modint &operator+=(const modint b){ v += b.v; if(v >= mod) v -= mod; return *this; } modint &operator-=(const modint b){ v -= b.v; if(v < 0) v += mod; return *this; } modint &operator*=(const modint b){v = v*b.v%mod; return *this;} modint &operator/=(modint b){ //b!=0 mod素数が必須. assert(b.v != 0); (*this) *= b.pow(mod-2); return *this; } modint pow(long long n)const{ modint ret = 1,p = v; if(n < 0) p = p.inv(),n = -n; while(n){ if(n&1) ret *= p; p *= p; n >>= 1; } return ret; } modint inv()const{return pow(mod-2);} //素数mod必須. modint &operator++(){*this += 1; return *this;} modint &operator--(){*this -= 1; return *this;} modint operator++(int){modint ret = *this; *this += 1; return ret;} modint operator--(int){modint ret = *this; *this -= 1; return ret;} friend bool operator==(const modint a,const modint b){return a.v==b.v;} friend bool operator!=(const modint a,const modint b){return a.v!=b.v;} friend bool operator<(const modint a,const modint b){return a.v=(const modint a,const modint b){return a.v>=b.v;} friend bool operator>(const modint a,const modint b){return a.v>b.v;} friend ostream &operator<<(ostream &os,const modint a){return os<>(istream &is,modint &a){ //入力はmodをとってくれる. long long x; is >> x; x %= mod; a = modint(x); return is; } }; using mint = modint<998244353>; const long long mod = 998244353; struct SS{ mint len,x2,x1; }; using FF = mint; class LazySegmentTree{ //ACL超参考にしてる というかパクリ. //verify十分だけど注意. private: vector dat; vector lazy; public: int siz = -1,n = -1,log = 0; SS op(SS a,SS b){return {a.len+b.len,a.x2+b.x2,a.x1+b.x1};} SS mapping(FF f, SS x){ if(f == 0) return x; return {x.len,x.x2 + x.x1*f*2 + x.len*f*f,x.x1 + x.len*f}; } FF composition(FF f, FF g){return f+g;} SS e(){return {0,0,0};} FF id(){return 0;} //op区間演算 mapping lazy→data composition lazy→lazy //e 単位元 id map(id,a)=a LazySegmentTree(int N){init(N);} LazySegmentTree(const vector &A){//配列サイズに合わせる. siz = 1; n = A.size(); log = 0; while(siz < n) siz <<= 1,log++; dat.resize(siz*2,e()); lazy.resize(siz,id()); for(int i=0; i0; i--) merge(i); } void init(int N){ //単位元になる. siz = 1; n = N; log = 0; while(siz < n) siz *= 2,log++; dat.assign(siz*2,e()); lazy.assign(siz,id()); } void init(const vector &A){ //配列サイズに合わせる. siz = 1; n = A.size(); log = 0; while(siz < n) siz <<= 1,log++; dat.resize(siz*2,e()); lazy.assign(siz,id()); for(int i=0; i0; i--) merge(i); } private: void eval(int u,FF f){ //u番目にfを適用したあと保留. if(u == 0) return; dat.at(u) = mapping(f,dat.at(u)); if(u < siz) lazy.at(u) = composition(f,lazy.at(u)); } void spread(int u){ //uにあるFF保留を伝播. if(u == 0 || id() == lazy.at(u)) return; eval(2*u,lazy.at(u)); eval(2*u+1,lazy.at(u)); lazy.at(u) = id(); } void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ. public: void set(int pos,SS x){ //1点変更. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); dat.at(pos) = x; while(pos > 1) pos >>= 1,merge(pos); } void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); dat.at(pos) = mapping(f,dat.at(pos)); while(pos > 1) pos >>= 1,merge(pos); } void update(int l,int r,FF f){ //区間更新. assert(0 <= l && l <= r && r <= n); if(l == r) return; l += siz; r += siz; for(int i=log; i>0; i--){ if(((l>>i)<>i); if(((r>>i)<>i); } int memoL = l,memoR = r; while(l < r){ if(l&1) eval(l++,f); if(r&1) eval(--r,f); l >>= 1; r >>= 1; } l = memoL,r = memoR; while((l&1) == 0) l >>= 1; while((r&1) == 0) r >>= 1; r--; //-1注意. while(l > 1) l >>= 1,merge(l); while(r > 1) r >>= 1,merge(r); } SS get(int pos){ //1点取得. assert(0 <= pos && pos < n); pos += siz; for(int i=log; i>0; i--) spread(pos>>i); return dat.at(pos); } SS rangeans(int l,int r){ //区間取得. assert(0 <= l && l <= r && r <= n); if(l == r) return e(); l += siz; r += siz; for(int i=log; i>0; i--){ if(((l>>i)<>i); if(((r>>i)<>i); } SS retl = e(),retr = e(); while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS allrange(){return dat.at(1);} //全体取得. int maxright(const function f,int l = 0){ assert(0 <= l && l <= n && f(e())); if(l == n) return n; l += siz; for(int i=log; i>0; i--) spread(l>>i); SS now = e(); do{ while(l%2 == 0) l >>= 1; SS next = op(now,dat.at(l)); if(f(next) == false){ while(l < siz){ spread(l); l <<= 1; next = op(now,dat.at(l)); if(f(next)) now = next,l++; } return l-siz; } now = next; l++; }while((l&-l) != l); return n; } int minleft(const function f,int r = -1){ if(r == -1) r = n; assert(0 <= r && r <= n && f(e())); if(r == 0) return 0; r += siz; for(int i=log; i>0; i--) spread((r-1)>>i); SS now = e(); do{ r--; while(r&1) r >>= 1; if(r == 0) r = 1; SS next = op(dat.at(r),now); if(f(next) == false){ while(r < siz){ spread(r); r <<= 1; r++; next = op(dat.at(r),now); if(f(next)) now = next,r--; } return r+1-siz; } now = next; }while((r&-r) != r); return 0; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector A(N); for(auto &a : A) cin >> a; mint answer = 0; vector X(N),Y(N); auto f = [&](auto f,int l,int r) -> void { if(l+1 == r) return; int m = (l+r)/2; f(f,l,m),f(f,m,r); vector give(r-m); { int big = 0,small = 1001001001; for(int i=m; i> B,S; for(int i=r-1; i>=m; i--) B.push({i,i+1,X.at(i)}),S.push({i,i+1,Y.at(i)}); for(int i=m-1,big=0,small=1001001001; i>=l; i--){ big = max(big,A.at(i)),small = min(small,A.at(i)); { int L = m,R = m; while(B.size()){ auto [L2,R2,v] = B.top(); if(big >= v){ if(big-v) Z.update(L2-m,R2-m,big-v); B.pop(),R = R2; } else break; } if(L != R) B.push({L,R,big}); } { int L = m,R = m; while(S.size()){ auto [L2,R2,v] = S.top(); if(small <= v){ if(v-small) Z.update(L2-m,R2-m,v-small); S.pop(),R = R2; } else break; } if(L != R) S.push({L,R,small}); } answer += Z.allrange().x2; } }; f(f,0,N); cout << answer << endl; }