#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
#define i128 __int128
using namespace std; 
const int N = 1e6 + 7;
int n, q; 
int a[N];
int ql[N], qr[N];
vi vc[N];
template < int N > struct fenwt {
	using F = long long ;
	F a[N + 1];
	void add (int x, F w) {
		for (; x <= N; x += x & -x) a[x] += w;
	}
	F query (int x) {
		F ret = 0;
		for (; x; x -= x & -x) ret += a[x];
		return ret;
	}
	F get (int l, int r) {
		if(l > r) return 0;
		return query (r) - query (l - 1);
	}
} ;

fenwt < N > F;

int stk[N], cnt[N], tp;
int ans[N];
vector < pair < int, int > > adds[N];
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> q;
	L(i, 1, n) {
		cin >> a[i];
	}
	L(t, 1, q) {
		cin >> ql[t] >> qr[t];
		vc[ql[t]].emplace_back(t);
	}
	stk[0] = n + 1;
	R(p, n, 1) {
		while(tp && a[p] < a[stk[tp]]) {
			for(auto&u : adds[tp])
				F.add(u.first, -u.second);
			--tp;
		}
		if(tp && a[stk[tp]] == a[p]) {
			++cnt[tp];
		} else {
			stk[++tp] = p, cnt[tp] = 1, adds[tp].clear();
		}
		int cp = stk[tp - 1] - 1, c = 0;
		while(cp <= n && c < cnt[tp]) ++cp, c += a[cp] > a[p];
		--c;
		int vl = stk[tp - 1] - cnt[tp] + 1, vr = cp;
		F.add(vl, 1), F.add(vr, -1);
		adds[tp].emplace_back(vl, 1), adds[tp].emplace_back(vr, -1);
		for(auto&t : vc[p]) {
			ans[t] = F.query(qr[t]);
		}
	}
	
	L(i, 1, q) cout << qr[i] - ql[i] - ans[i] << '\n';
	return 0;
}