#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &x){
	int ch = getchar(); x = 0;
	for(;ch < '0' || ch > '9';ch = getchar());
	for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} const int N = 25003;
int n, q, a[N], h[N], pl[N], pr[N], sl[N], sr[N], ans;
int ok(int l, int r){
	if(a[l] < a[r]) return pl[r] == l && sr[l] == r;
	return pr[l] == r && sl[r] == l;
}
void work(int l, int r){
	if(a[l] < a[r]){
		if(a[l] > a[pl[r]]){
			ans -= ok(l, sr[l]) + ok(pl[r], r);
			sr[l] = r; pl[r] = l; ++ ans;
		}
	} else {
		if(a[r] > a[pr[l]]){
			ans -= ok(l, pr[l]) + ok(sl[r], r);
			pr[l] = r; sl[r] = l; ++ ans;
		}
	}
}
int main(){
	read(n); read(q);
	for(int i = 1;i <= n;++ i){h[i] = i; read(a[i]);}
	while(q --){
		int l, r; read(l); read(r);
		for(int i = upper_bound(h + 1, h + n + 1, l) - h;i <= r;++ i)
			while(h[i] > l) work(--h[i], i);
		printf("%d\n", ans);
	}
}