#include<bits/stdc++.h>
using namespace std;
#define Re register int

const int N = 25005;
int n, m, ans, a[N], d[N], lpre[N], lsuf[N], rpre[N], rsuf[N];

inline int read()
{
	char c = getchar();
	int ans = 0;
	while (c < 48 || c > 57) c = getchar();
	while (c >= 48 && c <= 57) ans = (ans << 3) + (ans << 1) + (c ^ 48), c = getchar();
	return ans;
}

inline void write(int x)
{
	int num = 0;
	char sc[15];
	if (!x) sc[num = 1] = 48;
	while (x) sc[++num] = x % 10 + 48, x /= 10;
	while (num) putchar(sc[num--]);
	putchar('\n');
}

inline void add1(int x, int y)
{
	++ans, rsuf[x] = y, lpre[y] = x;
}

inline void add2(int x, int y)
{
	++ans, rpre[x] = y, lsuf[y] = x;
}

inline void cut1(int x, int y)
{
	ans -= (rsuf[x] == y && lpre[y] == x);
}

inline void cut2(int x, int y)
{
	ans -= (rpre[x] == y && lsuf[y] == x);
}

inline void calc(int x, int y)
{
	if (a[x] < a[y])
	{
		if (a[x] > a[lpre[y]]) cut1(lpre[y], y), cut1(x, rsuf[x]), add1(x, y);
	}
	else
	{
		if (a[x] < a[lsuf[y]]) cut2(lsuf[y], y), cut2(x, rpre[x]), add2(x, y);
	}
}

int main()
{
	n = read(), m = read(), a[n + 1] = n + 1;
	for (Re i = 1; i <= n; ++i) a[i] = read(), d[i] = i, lsuf[i] = rsuf[i] = n + 1;
	while (m--)
	{
		int u = read(), v = read();
		int l = u, r = v, s = v + 1;
		while (l <= r)
		{
			int mid = l + r >> 1;
			if (d[mid] > u) s = mid, r = mid - 1;
			else l = mid + 1;
		}
		for (Re i = s; i <= v; ++i)
			while (d[i] > u) calc(--d[i], i);
		write(ans);
	}
	return 0;
}
