Shared code

//~ author      : Sumit Prajapati


#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+5;
const int MD = 1e9+7;
int n;
int a[MAXN];


vector<int> segm[4*MAXN];
void merge(vector<int>& A, vector<int>& B, vector<int>& to ) {
	int szA=A.size(),szB=B.size(),i=0,j=0;
	while(i<szA)
		to.push_back(A[i++]);
	while(j<szB) {
		if(B[j]>A.back()) {
			to.push_back(B[j]);
		}
		j++;
	}

}
void buildtree(int cur,int start,int end) {
	if(start==end) {
		//BASE CASE
		segm[cur].push_back(a[start]);
		return;
	}
	int mid=(start+end)>>1;
	buildtree(cur<<1,start,mid);
	buildtree((cur<<1)+1,mid+1,end);
	//MERGING STEP
	merge(segm[2*cur],segm[2*cur+1],segm[cur]);
}
pair<int,int> query(int cur,int start,int end,int qs,int qe, int threshold) {
    // cerr<<start<<" "<<end<<" ? "<<threshold<<"\n";
	if(start>=qs && end<=qe) {
		auto idx = upper_bound(segm[cur].begin(),segm[cur].end(), threshold);
		if(idx==segm[cur].end()) {
// 			cout<<start<<" "<<end<<" "<<threshold<<"> 0 -1\n";
			return {0, -1};
		}
		int cnt = segm[cur].end()-idx;
		int mx = segm[cur].back();
// 		cout<<start<<" "<<end<<" "<<threshold<<"| "<<cnt<<" "<<mx<<"\n";
		return {cnt, mx};
	}
	if(start>qe || end<qs)
		return {0, -1};          //INVALID RETURN
	int mid=(start+end)>>1;
	pair<int,int> A=query(2*cur,start,mid,qs,qe, threshold);
	pair<int,int> B=query(2*cur+1,mid+1,end,qs,qe, max(A.second, threshold));
	//MERGING STEP
	pair<int,int> res;
	res.first = A.first + B.first;
	res.second = max(A.second, B.second);
// 	cout<<start<<" "<<end<<" "<<threshold<<": "<<res.first<<" "<<res.second<<"\n";

	return res;
}
void solve() {
	int q;
	cin>>n>>q;
	for(int i = 1; i<=n; i++) {
		cin>>a[i];
	}
	buildtree(1,1,n);
	int l, r;
	for(int i = 1; i<=q; i++) {
		cin>>l>>r;
		cout<<query(1,1,n,l,r, -1).first<<"\n";
	}
}


int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	solve();

	return 0;
}