//#pragma GCC optimize("O3") #include using namespace std; #define ll long long #define rep(i,n) for (ll i=0;i<(ll)n;i++) #define rrep(i,n) for (ll i=n-1;i>=(ll)0;i--) #define loop(i,m,n) for(ll i=m;i<=(ll)n;i++) #define rloop(i,m,n) for(ll i=m;i>=(ll)n;i--) #define vl vector #define vvl vector> #define vdbg(a) rep(ii,a.size()){cout< struct SegTree{ ll size; ll tall; vector data; function p; //セグ木に乗せる値の初期値をa配列にし、putの関数をセグ木に乗せる、dをデフォルト値に。 SegTree(vector a,function put,T d) : data(power(2,logax(2,a.size())+1)) { size = data.size()/2; tall=logax(2,size)+1; p=put; ll tmp=size; data = vector(size*2,d); while(tmp!=0){ if(tmp==size)rep(i,a.size())data[tmp+i]=a[i]; else rep(i,tmp) data[tmp+i]=p(data[2*(tmp+i)],data[2*(tmp+i)+1]); tmp/=2; } } //更新、t番目の値をxにする。 void update(ll t,T x){ t+=size; while(t!=0){ if(t>=size)data[t]=x; else data[t]=p(data[2*t],data[2*t+1]); t/=2; } } //取得、l~r区間内の評価値を取得する。 T get(ll l,ll r){ //lとrが範囲外なら範囲内に正す l=max(0LL,l); r=min(r,size-1); r++; T ans=data[0]; ll pos=l+size; ll wid=1; //出来る限り上に上げきる。 while(l+(wid*2)<=r){ while(l%(wid*2)==0&&l+(wid*2)<=r)pos/=2,wid*=2; ans=p(ans,data[pos]); pos++; l+=wid; } //上げ終わったので今度は下げる while(l!=r){ while(l+wid>r)pos*=2,wid/=2; ans=p(ans,data[pos]); pos++; l+=wid; } return ans; } }; ll sums(ll a,ll b){ return a+b; } //メイン int main(){ ll n,q; cin>>n>>q; vl a(n+1); loop(i,1,n)cin>>a[i],a[i]--; a[0]=n; vl prevbig(n+1,0); vvl inv(n+1); vector> st; st.push_back({n,0}); loop(i,1,n){ while(st.back().first>> query(n+1); rep(i,q){ ll l,r; cin>>l>>r; query[l].push_back({r,i}); } SegTree seg(vl(n+1,0),sums,0); vl ans(q,0); rloop(i,n,1){ rep(j,inv[i].size()){ seg.update(inv[i][j],1); } rep(j,query[i].size()){ ll right=query[i][j].first; ll index=query[i][j].second; ans[index]=seg.get(i,right); } } rep(i,q)cout<