#include #include #ifndef IO_HPP #define IO_HPP #include #include #include #include #include #include #include #include #include using namespace std; templateistream &operator>>(istream&,pair&); templateistream &operator>>(istream&,tuple&a); templateistream &operator>>(istream&is,vector&a); templateistream &operator>>(istream&is,array&a); template istream &operator>>(istream&is,pair&a){ is>>a.first>>a.second; return is; } template void read_tuple(istream&is,tuple&a){ if constexpr(pos>::value){ is>>get(a); read_tuple(is,a); } } template istream &operator>>(istream&is,tuple&a){ read_tuple<0>(is,a); return is; } template istream &operator>>(istream&is,vector&a){ for(T&x:a)is>>x; return is; } template istream &operator>>(istream&is,array&a){ for(T&x:a)is>>x; return is; } templateostream &operator<<(ostream&os,const pair&); templateostream &operator<<(ostream&os,const tuple&); templateostream &operator<<(ostream&os,const vector&); templateostream &operator<<(ostream&os,priority_queue); templateostream &operator<<(ostream&os,queue); templateostream &operator<<(ostream&os,deque); templateostream &operator<<(ostream&os,stack); templateostream &operator<<(ostream&os,const array&); templateostream &operator<<(ostream&os,const map&); templateostream &operator<<(ostream&os,const unordered_map&); templateostream &operator<<(ostream&os,const set&); templateostream &operator<<(ostream&os,const multiset&); templateostream &operator<<(ostream&os,const unordered_set&); template ostream &operator<<(ostream&os,const pair&a){ os< void write_tuple(ostream&os,const tuple&a){ if constexpr(pos>::value){ if constexpr(pos>0)os<<' '; os<(a); write_tuple(os,a); } } template ostream &operator<<(ostream&os,const tuple&a){ write_tuple<0>(os,a); return os; } template ostream &operator<<(ostream&os,const vector&a){ os<<'{'; for(int i=0;i<(int)a.size();i++){ os< ostream &operator<<(ostream&os,priority_queuea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,queuea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,dequea){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,stacka){ os<<'{'; if(!a.empty()){ os< ostream &operator<<(ostream&os,const array&a){ os<<'{'; for(int i=0;i<(int)a.size();i++){ os< ostream &operator<<(ostream&os,const map&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<"{["<first<<","<second<<']'; while(++itr!=a.end())os<<",["<first<<','<second<<']'; os<<'}'; return os; } template ostream &operator<<(ostream&os,const unordered_map&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<"{["<first<<","<second<<']'; while(++itr!=a.end())os<<",["<first<<','<second<<']'; os<<'}'; return os; } template ostream &operator<<(ostream&os,const set&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } template ostream &operator<<(ostream&os,const multiset&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } template ostream &operator<<(ostream&os,const unordered_set&a){ if(a.empty()){ os<<"{}"; return os; } auto itr=a.begin(); os<<'{'<<*itr; while(++itr!=a.end())os<<','<<*itr; os<<'}'; return os; } #endif using namespace std; using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templatevoid operator++(pair&a,int){a.first++,a.second++;} templatevoid operator--(pair&a,int){a.first--,a.second--;} templatevoid operator++(vector&a,int){for(auto &i:a)i++;} templatevoid operator--(vector&a,int){for(auto &i:a)i--;} using vref=typename vector::reference; vref operator|=(vref a,bool b){a=a|b;return a;} vref operator&=(vref a,bool b){a=a&b;return a;} vref operator^=(vref a,bool b){a=a^b;return a;} #define overload3(_1,_2,_3,name,...) name #define rep1(i,n) for(int i=0;i<(int)(n);i++) #define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++) #define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__) #define reps(i,l,r) rep2(i,l,r) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcountll(x) #define fin(x) return cout<<(x)<<'\n',static_cast(0) #define yn(x) cout<<((x)?"Yes\n":"No\n") #define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end()) template inline int fkey(vector&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();} ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include #define SWITCH(a,b) (a) #else #define debug(...) static_cast(0) #define debugg(...) static_cast(0) #define SWITCH(a,b) (b) #endif struct Timer{ clock_t start; Timer(){ start=clock(); ios::sync_with_stdio(false); cin.tie(nullptr); cout<>testcase; for(int i=0;i #include #include constexpr bool isprime_constexpr(unsigned long long n){ if(n==998244353)return true; if(n==1000000007)return true; if(n<64)return 2891462833508853932ll>>n&1; if(n%2==0)return false; unsigned long long d=n-1; int s=0; while(!(d&1))d>>=1,s++; int q=63; while(!(d>>q))q--; unsigned long long r=n; for(int i=0;i<5;i++)r*=2-r*n; auto redc=[&r,&n](__uint128_t x)->unsigned long long { x=(x+__uint128_t((unsigned long long)x*-r)*n)>>64; return x>=n?x-n:x; }; __uint128_t r2=-__uint128_t(n)%n; unsigned long long one=redc(r2); for(unsigned long long base:{2,325,9375,28178,450775,9780504,1795265022}){ if(base%n==0)continue; unsigned long long a=base=redc((base%n)*r2); for(int i=q-1;i>=0;i--){ a=redc(__uint128_t(a)*a); if(d>>i&1)a=redc(__uint128_t(a)*base); } if(a==one)continue; for(int i=1;a!=n-one;i++){ if(i>=s)return false; a=redc(__uint128_t(a)*a); } } return true; } constexpr std::pairext_gcd(long long a,long long b){ if(b==0)return std::make_pair(1,0); auto [x,y]=ext_gcd(b,a%b); std::swap(x,y); return std::make_pair(x,y-a/b*x); } template constexpr std::pair inv_mod(T a,T b){ a%=b; if(a<0)a+=b; if(a==0)return std::make_pair(b,0); T s=b,t=a; T m0=0,m1=1; while(t){ T u=s/t; s-=t*u; m0-=m1*u; std::swap(s,t); std::swap(m0,m1); } if(m0<0)m0+=b/s; return std::make_pair(s,m0); } template struct modint{ static_assert(1<=m&&m<(1ull<<63)); using value_type=std::conditional_t<((m>>31)==0),uint32_t,uint64_t>; using mul_type=std::conditional_t<((m>>31)==0),uint64_t,__uint128_t>; private: value_type v; static constexpr value_type umod=m; constexpr modint sqrt_impl()const{ if(this->val()<=1)return *this; if(umod%8==1){ modint b=2; while(b.pow((umod-1)/2).val()==1)b++; value_type m2=umod-1; int e=0; while(m2%2==0)m2>>=1,e++; modint x=this->pow((m2-1)/2); modint y=(*this)*x*x; x*=*this; modint z=b.pow(m2); while(y.val()!=1){ int j=0; modint t=y; while(t.val()!=1)t*=t,j++; z=z.pow((value_type(1))<<(e-j-1)); x*=z; z*=z; y*=z; e=j; } return x; } else if(umod%8==5){ modint res=this->pow((umod+3)/8); if((res*res).val()==this->val())return res; else return res*modint(2).pow((umod-1)/4); } else return this->pow((umod+1)/4); } template||std::is_same_v,std::nullptr_t> =nullptr> static constexpr value_type take_mod(U x){ if constexpr(std::numeric_limits::max()>61)+(x&umod); if(res>=umod)res-=umod; return res; } if constexpr(umod==(1ull<<61)-(1ull<<24)+1){ value_type high=x>>61,low=x&((1ull<<61)-1); mul_type t=low+(mul_type(high)<<24)-high; high=t>>61,low=t&((1ull<<61)-1); low=low+(mul_type(high)<<24)-high; if(low>=umod)low-=umod; return low; } return x%umod; } public: constexpr modint():v(0){} template||std::is_same_v,std::nullptr_t> =nullptr> constexpr modint(U x){ x%=std::make_signed_t(umod); v=x>=0?x:x+umod; } template||std::is_same_v,std::nullptr_t> =nullptr> constexpr modint(U x):v(take_mod(x)){} static constexpr value_type mod(){return umod;} static constexpr modint zero(){return raw(0);} static constexpr modint one(){ if constexpr(m==1)return raw(0); else return raw(1); } template static constexpr modint raw(U x){ modint res; res.v=x; return res; } constexpr std::make_signed_t val()const{return v;} constexpr modint &operator+=(const modint&b){ this->v+=b.v; if(this->v>=umod)this->v-=umod; return *this; } constexpr modint &operator-=(const modint&b){ this->v-=b.v; if(this->v>=umod)this->v+=umod; return *this; } constexpr modint &operator*=(const modint&b){ this->v=take_mod(mul_type(this->v)*mul_type(b.v)); return *this; } constexpr modint &operator/=(const modint&b){return *this*=b.inv();} constexpr modint operator+()const{return *this;} constexpr modint operator-()const{return modint()-*this;} friend constexpr modint operator+(const modint&a,const modint&b){return modint(a)+=b;} friend constexpr modint operator-(const modint&a,const modint&b){return modint(a)-=b;} friend constexpr modint operator*(const modint&a,const modint&b){return modint(a)*=b;} friend constexpr modint operator/(const modint&a,const modint&b){return modint(a)/=b;} constexpr auto operator<=>(const modint&)const=default; constexpr modint operator++(int){ modint res=*this; this->v++; if(this->v==umod)this->v=0; return res; } constexpr modint operator--(int){ modint res=*this; if(this->v==0)this->v=umod; this->v--; return res; } template constexpr modint pow(U k)const{ if constexpr(std::is_signed_v){ assert(0<=k); } modint res=1,a(*this); while(k){ if(k&1)res*=a; a*=a; k>>=1; } return res; } constexpr modint inv()const{ if constexpr(isprime_constexpr(umod)){ if(std::is_constant_evaluated()){ if(v==0){ throw "no inverse"; } } else assert(v!=0); return pow(umod-2); } else{ modint res; auto [g,x]=inv_mod>(this->v,umod); if(std::is_constant_evaluated()){ if(g!=1){ throw "no inverse"; } } else assert(g==1); res.v=x; return res; } } std::optionalsqrt()const{ if(this->val()<=1||this->pow((umod-1)/2)==1)return std::make_optional(this->sqrt_impl()); else return std::nullopt; } friend std::istream &operator>>(std::istream&is,modint&b){ long long a; is>>a; b=modint(a); return is; } friend std::ostream &operator<<(std::ostream&os,const modint&b){ os< struct std::hash>{ std::size_t operator()(modintx)const{ return std::hash::value_type>(x.val()); } }; using mint998=modint<998244353>; using mint107=modint<1000000007>; using mint61=modint<2305843009213693951>; using mint6124=modint<2305843009196916737>; template struct fast_stack{ private: T *st; int p; public: fast_stack(int n):p(0){ st=new T[n]; } fast_stack(){} inline void push(const T&x){st[p++]=x;} template inline T& emplace(Args&&...args){ st[p++]=T(std::forward(args)...); return st[p-1]; } inline T& pop(){return st[--p];} inline T top()const{return st[p-1];} inline T& top(){return st[p-1];} inline int size()const{return p;} inline bool empty()const{return !p;} inline void clear(){p=0;} ~fast_stack(){delete[] st;} }; template std::vectorcartesian_tree(const std::vector&a){ int n=a.size(); std::vectorres(n,-1); fast_stackst(n); for(int i=0;i=a[i]){ ls=x; st.pop(); } else break; } else{ if(a[x]<=a[i]){ ls=x; st.pop(); } else break; } } if(ls!=-1)res[ls]=i; if(!st.empty())res[i]=st.top(); st.push(i); } return res; } #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} template struct SparseTable{ using S=typename M::S; private: std::vectordat,prefix,suffix; std::vector>sp; public: SparseTable(){} SparseTable(std::vectora):dat(a){ int n=a.size(); n=(n+(1<d2(n>>L,M::e()); for(int i=0;i<(int)d2.size();i++){ for(int j=0;j<(1<>L);i++){ for(int j=1;j<(1<>L)-1;i>=0;i--){ for(int j=(1<=1;j--)suffix[(i<=j-w;k--)sp[i][k]=M::op(d2[k],sp[i][k+1]); int r=std::min(d2.size(),j+w); for(int k=j+1;k>L,rid=r>>L; if(lid==rid){ S ret=M::e(); for(int i=l;i<=r;i++)ret=M::op(ret,dat[i]); return ret; } else{ lid++; rid--; S mid=M::e(); if(lid==rid)mid=sp[0][lid]; else if(lid::min()> struct MonoidMax{ using S=T; static inline S op(const S&x,const S&y){return x static inline S pow(const S&x,U){return x;} }; template::max()> struct MonoidMin{ using S=T; static inline S op(const S&x,const S&y){return x static inline S pow(const S&x,U){return x;} }; template struct LazySegmentTree{ private: using S=typename M::M1::S; using F=typename M::M2::S; int n,z; int log2n; std::vectordat; std::vectorlazy; inline void propagate(int i,const F&f){ dat[i]=M::act(dat[i],f); if(il;j--)push(i>>j); } inline void path_update(int i){ int l=lsb(i); i>>=(l+1); while(i){ update(i); i>>=1; } } public: LazySegmentTree():n(0),z(0),log2n(0){} explicit LazySegmentTree(int n_):n(n_),z(ceil_pow2(n_)){ log2n=msb(z); dat.resize(z*2,M::M1::e()),lazy.resize(z*2,M::M2::e()); } explicit LazySegmentTree(const std::vector&init):n(init.size()),z(ceil_pow2((int)init.size())){ log2n=msb(z); dat.resize(z*2,M::M1::e()),lazy.resize(z*2,M::M2::e()); for(int i=0;i=1;i--)update(i); } LazySegmentTree(int n_,S init):LazySegmentTree(std::vector(n_,init)){} void set(int i,const S&x){ assert(0<=i&&i0;j--)push(i>>j); dat[i]=x; i>>=1; while(i){ update(i); i>>=1; } } S get(int i){ assert(0<=i&&i0;j--)push(i>>j); return dat[i]; } void apply(int l,int r,const F&f){ assert(0<=l&&l<=r&&r<=n); if(r==n)r=z; l+=z,r+=z; path_push(l),path_push(r); int l2=l,r2=r; while(l>=1,r>>=1; } path_update(l2),path_update(r2); } S prod(int l,int r){ assert(0<=l&&l<=r&&r<=n); if(r==n)r=z; l+=z,r+=z; path_push(l),path_push(r); S left=M::M1::e(),right=M::M1::e(); while(l>=1,r>>=1; } return M::M1::op(left,right); } inline S all_prod()const{return dat[1];} template int max_right(int l,const Func&f){ assert(0<=l&&l<=n); if(l==n)return n; l+=z; for(int i=log2n;i>=1;i--)push(l>>i); S now=M::M1::e(); do{ l>>=lsb(l); S nxt=M::M1::op(now,dat[l]); if(f(nxt))now=nxt,l++; else{ while(l int min_left(int r,const Func&f){ assert(0<=r&&r<=n); if(r==0)return 0; r+=z; for(int i=log2n;i>=1;i--)push((r-1)>>i); S now=M::M1::e(); do{ r--; while(r>1&&(r&1))r>>=1; S nxt=M::M1::op(dat[r],now); if(f(nxt))now=nxt; else{ while(rget_all(){ for(int i=1;i(dat.begin()+z,dat.begin()+z+n); } friend std::ostream &operator<<(std::ostream&os,const LazySegmentTree&seg){ std::vectorlazy2(seg.lazy); for(int i=0;i struct MonoidAdd{ using S=T; static inline S op(S x,S y){return x+y;} static inline S e(){return T();} static inline S inverse(S x){return -x;} static inline void revS(S&x){} template static inline S pow(S x,U p){return x*p;} }; template struct MonoidMul{ using S=T; static inline S op(S x,S y){return x*y;} static inline S e(){ if constexpr(requires(){T::one();})return T::one(); else return T(1); } static inline void revS(S&){} static inline S inverse(S x){return x.inv();} }; template,std::nullptr_t> = nullptr> T mex(const std::vector&a){ int n=a.size(); std::vectorseen(n,false); for(int i=0;i; using M2=MonoidMul; static mint act(mint x,mint f){return x*f;} }; mint solve(vectora){ int n=a.size(); vectorc=cartesian_tree(a); vectorleft(n,-1),right(n,-1); int root=-1; rep(i,n){ if(c[i]==-1)root=i; else (ivoid { if(x==-1)return; res+=mint(a[x]).pow(2)*(x-l+1)*(r-x); self(self,l,x,left[x]); self(self,x+1,r,right[x]); }; dfs(dfs,0,n,root); return res; } mint solve2(vectora){ int n=a.size(); LazySegmentTreeseg(n); mint res=0; vector>stmx,stmn; int r=0; auto yarumx=[&](){ while(stmx.size()>=2){ auto&[i,vi]=stmx[stmx.size()-2]; auto&[j,vj]=stmx[stmx.size()-1]; if(vi=2){ auto&[i,vi]=stmn[stmn.size()-2]; auto&[j,vj]=stmn[stmn.size()-1]; if(vi>vj){ seg.apply(i,j,mint(vj)/vi); vi=vj; stmn.pop_back(); } else break; } }; rep(i,n){ stmx.emplace_back(i,a[i]); stmn.emplace_back(i,a[i]); seg.set(i,mint(a[i]).pow(2)); r++; yarumx(); yarumn(); res+=seg.all_prod(); } return res*-2; } void SOLVE(){ int n; cin>>n; vectora(n); cin>>a; vectoraddx(n); rep(i,n)addx[i]=mint(-a[i]).val(); ll x=mex(addx); rep(i,n)a[i]+=x; mint ans=solve(a); rep(i,n)a[i]=-a[i]; ans+=solve(a); rep(i,n)a[i]=-a[i]; ans+=solve2(a); cout<