#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define rep(i, s, t) for (int i = s; i <= t; ++i)
#define per(i, s, t) for (int i = t; i >= s; --i)

const int N = 1e6 + 5;
const int M = N * 21;

int n, q;
int a[N], pos[N];
vector<pair<int, int>> qry[N];
int ans[N];
int stk[N], top;

int t[N];
inline int lowbit(int x) { return x & (-x); }
inline void add(int x, int val) { for(int x0 = x; x0 <= n; x0 += lowbit(x0)) t[x0] += val; }
inline void add(int l, int r, int val) { add(l, val), add(r+1, -val); }
inline int query(int x) { int ret = 0; for(int x0 = x; x0; x0 -= lowbit(x0)) ret += t[x0]; return ret; }

int rt[N], ls[M], rs[M], mi[M], tt;

inline int newnode(int o) {
	int e = ++tt;
	ls[e] = ls[o], rs[e] = rs[o], mi[e] = mi[o];
	return e;
}

inline void pushup(int o) {
	mi[o] = min(mi[ls[o]], mi[rs[o]]);
}

inline void modify(int& o1, int o2, int p, int val, int l, int r) {
	o1 = newnode(o2);
	if(l == r) {
		mi[o1] = val;
		return;
	}
	int mid = l + r >> 1;
	if(p <= mid) modify(ls[o1], ls[o2], p, val, l, mid);
	else modify(rs[o1], rs[o2], p, val, mid+1, r);
	pushup(o1);
}

inline int query(int o, int ql, int qr, int l, int r) {
	if(!o || ql > qr) return n+1;
	if(ql <= l && r <= qr) {
		return mi[o];
	}
	int mid = l + r >> 1;
	int res = n+1;
	if(ql <= mid) res = min( res, query(ls[o], ql, qr, l, mid));
	if(mid < qr) res = min(res, query(rs[o], ql, qr, mid+1, r));
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cout << fixed << setprecision(15); 
	cerr << fixed << setprecision(15);


	cin >> n >> q;
	mi[0] = n+1;
	rep(i, 1, n) cin >> a[i];
	rep(i, 1, q) {
		int l, r; cin >> l >> r;
		qry[l].emplace_back(r, i);
	}
	per(i, 1, n) {
		modify(rt[i], rt[i+1], a[i], i, 1, n);
	}
	stk[0] = n+1;
	per(i, 1, n) {
		while(top && a[stk[top]] > a[i]) {
			add(stk[top], pos[stk[top]], -1);
			--top;
		}
		if(a[i] == a[stk[top]]) {
			pos[i] = query(rt[pos[stk[top]]+2], a[i]+1, n, 1, n) - 1;
		} else {
			pos[i] = query(rt[stk[top]], a[i]+1, n, 1, n) - 1;
		}
		add(i, pos[i], 1);
		stk[++top] = i;
		for(auto [r, id] : qry[i]) ans[id] = r-i+1 - query(r);
	}
	rep(i, 1, q) {
		cout << ans[i] << "\n";
	}


	return 0;
}