/* https://codeforces.com/blog/entry/89644?#comment-781096 (ecnerwala) */
#include <stdio.h>

#define N	25000

int main() {
	static int aa[N], ll[N], rr[N], lu[N], ld[N], ru[N], rd[N];
	int n, q, ans, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	for (i = 0; i < n; i++)
		ll[i] = rr[i] = i, lu[i] = ld[i] = ru[i] = rd[i] = -1;
	ans = 0;
	while (q--) {
		int l, r;

		scanf("%d%d", &l, &r), l--, r--;
		for (i = r; ll[i] > l; i--)
			while (ll[i] > l) {
				ll[i]--;
				if (aa[ll[i]] > aa[i]) {
					if (lu[i] == -1 || aa[lu[i]] > aa[ll[i]]) {
						if (lu[i] != -1 && rd[lu[i]] == i)
							ans--;
						lu[i] = ll[i];
						if (rd[lu[i]] == i)
							ans++;
					}
				} else {
					if (ld[i] == -1 || aa[ld[i]] < aa[ll[i]]) {
						if (ld[i] != -1 && ru[ld[i]] == i)
							ans--;
						ld[i] = ll[i];
						if (ru[ld[i]] == i)
							ans++;
					}
				}
			}
		for (i = l; rr[i] < r; i++)
			while (rr[i] < r) {
				rr[i]++;
				if (aa[rr[i]] > aa[i]) {
					if (ru[i] == -1 || aa[ru[i]] > aa[rr[i]]) {
						if (ru[i] != -1 && ld[ru[i]] == i)
							ans--;
						ru[i] = rr[i];
						if (ld[ru[i]] == i)
							ans++;
					}
				} else {
					if (rd[i] == -1 || aa[rd[i]] < aa[rr[i]]) {
						if (rd[i] != -1 && lu[rd[i]] == i)
							ans--;
						rd[i] = rr[i];
						if (lu[rd[i]] == i)
							ans++;
					}
				}
			}
		printf("%d\n", ans);
	}
	return 0;
}
