#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 25005;
int n, q, a[maxn];
int lpos[maxn], rpos[maxn];
int lpre[maxn], lnxt[maxn], rpre[maxn], rnxt[maxn];
int main() {
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++) {
		lpos[i] = rpos[i] = i;
		lpre[i] = rpre[i] = lnxt[i] = rnxt[i] = -1;
	}
	int res = 0;
	for(int i = 1, L, R; i <= q; i++) {
		scanf("%d%d", &L, &R);
		for(int j = L; j <= R; j++) {
			if(rpos[j] >= R) break;
			for(int k = rpos[j] + 1; k <= R; k++) {
				if(a[k] < a[j]) {
					if(rpre[j] == -1) {
						rpre[j] = k;
						if(lnxt[k] == j) res++;
					} 
					else if(a[rpre[j]] < a[k]) {
						int x = rpre[j];
						if(lnxt[x] == j) res--;
						rpre[j] = k;
						if(lnxt[k] == j) res++;
					}
				}
				else {
					if(rnxt[j] == -1) {
						rnxt[j] = k;
						if(lpre[k] == j) res++;
					}
					else if(a[rnxt[j]] > a[k]) {
						int x = rnxt[j];
						if(lpre[x] == j) res--;
						rnxt[j] = k;
						if(lpre[k] == j) res++;
					}
				}
			}
			rpos[j] = R;
		}
		for(int j = R; j >= L; j--) {
			if(lpos[j] <= L) break;
			for(int k = lpos[j] - 1; k >= L; k--) {
				if(a[k] < a[j]) {
					if(lpre[j] == -1) {
						lpre[j] = k;
						if(rnxt[k] == j) res++;
					}
					else if(a[lpre[j]] < a[k]) {
						int x = lpre[j];
						if(rnxt[x] == j) res--;
						lpre[j] = k;
						if(rnxt[k] == j) res++;
					}
				}
				else {
					if(lnxt[j] == -1) {
						lnxt[j] = k;
						if(rpre[k] == j) res++;
					}
					else if(a[lnxt[j]] > a[k]) {
						int x = lnxt[j];
						if(rpre[x] == j) res--;
						lnxt[j] = k;
						if(rpre[k] == j) res++;
					}
				}
			}
			lpos[j] = L;
		}
		printf("%d\n", res);
	}
	return 0;
}