#include using namespace std; typedef unsigned long long int ull; typedef long long int ll; typedef pair pll; typedef long double D; typedef complex P; #define F first #define S second const ll E=1e18+7; const ll MOD=1000000007; templateistream & operator >> (istream &i,pair &A){i>>A.F>>A.S; return i;} templateistream & operator >> (istream &i,vector &A){for(auto &I:A){i>>I;} return i;} templateostream & operator << (ostream &o,const pair &A){o<ostream & operator << (ostream &o,const vector &A){ll i=A.size(); for(auto &I:A){o<vector & cset(vector &A,T e=T()){for(auto &I:A){I=e;} return A;} #ifndef SEGMENT_TREE #define SEGMENT_TREE template class SegTree{ private: typedef function MergeData; typedef function MergeMono; typedef function Culc; typedef function UpdateQuery; //data,mono,left,right true::Data,Monoに作用する false::子に降りる int size,high; vector left,right; vector dv; vector mv; Data de; Mono me; MergeData df; MergeMono mf; Culc cf; inline bool nx(int &idx){ while(idx&1){idx>>=1; if(idx){reculc(idx);}} return idx?idx|=1:idx; } inline void reculc(int idx){ dv[idx]=dv[idx<<1]; df(dv[idx],dv[(idx<<1)|1]); cf(dv[idx],mv[idx]); } inline void down(int idx){ cf(dv[idx<<1],mv[idx]); mf(mv[idx<<1],mv[idx]); cf(dv[(idx<<1)|1],mv[idx]); mf(mv[(idx<<1)|1],mv[idx]); mv[idx]=me; } public: SegTree(Data de,Mono me,MergeData df,MergeMono mf,Culc cf,int n=0):de(de),me(me),df(df),mf(mf),cf(cf){init(n);} void init(int n){ size=1; high=0; while(size0;i--){left[i]=left[i<<1]; right[i]=right[(i<<1)|1];} } void build(const vector &ary){ int n=ary.size(); init(n); for(int i=0;i0;i--){dv[i]=dv[i<<1]; df(dv[i],dv[(i<<1)|1]);} } //[lf,rg) Data query(int lf,int rg){ Data ret=de; int idx=1; bool j=true; while(j){ if(right[idx]<=lf || rg<=left[idx]){j&=nx(idx);} else if(lf<=left[idx] && right[idx]<=rg){df(ret,dv[idx]); j&=nx(idx);} else{down(idx); idx<<=1;} } return ret; } void update(int lf,int rg,Mono m){ int idx=1; bool j=true; while(j){ if(right[idx]<=lf || rg<=left[idx]){j&=nx(idx);} else if(lf<=left[idx] && right[idx]<=rg){ cf(dv[idx],m); mf(mv[idx],m); j&=nx(idx); } else{down(idx); idx<<=1;} } } void update(int lf,int rg,UpdateQuery br){ int idx=1; bool j=true; while(j){ if(right[idx]<=lf || rg<=left[idx]){j&=nx(idx);} else if(lf<=left[idx] && right[idx]<=rg){ if(br(dv[idx],mv[idx],left[idx],right[idx])){j&=nx(idx);} else{down(idx); idx<<=1;} } else{down(idx); idx<<=1;} } } }; #endif /*SEGMENT_TREE*/ int main(){ auto df=[](pll &a,pll &b)->void{a.F+=b.F; a.S+=b.S;}; auto mf=[](ll &a,ll &b)->void{a+=b;}; auto cf=[](pll &a,ll &b)->void{a.F+=b*a.S;}; pll de={0,0}; ll me=0; ll n,q; cin>>n>>q; vector A(n); cin>>A; SegTree Tr(de,me,df,mf,cf); Tr.build(vector(n,{0,1})); vector> Q(q); for(int i=0;i>c>>Q[i].F; Q[i].S=i; Q[i].F.F--; Q[i].F.S--; } stack S; sort(Q.begin(),Q.end(),greater>()); vector ans(q,0); int idx=0; for(ll i=n-1;i>=0;i--){ while(!S.empty() && S.top().F