#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
class IO {
    char ibuf[1 << 16], obuf[1 << 16], *ipl = ibuf, *ipr = ibuf, *op = obuf;
    public:
    ~IO() { write(); }
    void read() { if (ipl == ipr) ipr = (ipl = ibuf) + fread(ibuf, 1, 1 << 15, stdin); }
    void write() { fwrite(obuf, 1, op - obuf, stdout), op = obuf; }
    char getchar() { return (read(), ipl != ipr) ? *ipl++ : EOF; }
    void putchar(char c) { *op++ = c; if (op - obuf > (1 << 15)) write(); }
    template <typename V> IO& operator >> (V& v) {
        int s = 1; char c = getchar(); v = 0;
        for (; !isdigit(c); c = getchar()) if (c == '-') s = -s;
        for (; isdigit(c); c = getchar()) v = (v << 1) + (v << 3) + (c ^ 48);
        return v *= s, *this;
    }
    IO& operator << (char c) { return putchar(c), *this; }
    template <typename V> IO& operator << (V v) {
        if (!v) putchar('0'); if(v < 0) putchar('-'), v = -v;
        char stk[100], *top = stk;
        for (; v; v /= 10) *++top = v % 10 + '0';
        while (top != stk) putchar(*top--); return *this;
    }
} io;
constexpr int N = 1e6 + 5;
int n, q, a[N], f[N][20], pos[N];
struct seg {
	int mxa[N << 2], taga[N << 2], mxb[N << 2], tagb[N << 2];
	bool ok[N << 2], atob[N << 2];
	#define ls k << 1
	#define rs k << 1 | 1
	void push_up(int k)
	{
		ok[k] = ok[ls] || ok[rs];
		mxa[k] = max(mxa[ls], mxa[rs]);
		mxb[k] = max(mxb[ls], mxb[rs]);
	}
	void pusha(int k, int v)
	{
		if (!ok[k]) return;
		mxa[k] = max(mxa[k], v);
		taga[k] = max(taga[k], v);
	}
	void pushb(int k, int v)
	{
		if (!ok[k]) return;
		mxb[k] = max(mxb[k], v);
		tagb[k] = max(tagb[k], v);
	}
	void pushto(int k)
	{
		if (!ok[k]) return;
		atob[k] = 1;
		mxb[k] = max(mxb[k], mxa[k]);
		tagb[k] = max(tagb[k], taga[k]);
	}
	void push_down(int k)
	{
		if (!ok[k]) return;
		if (atob[k]) {
			pushto(ls);
			pushto(rs);
			atob[k] = 0;
		}
		if (taga[k]) {
			pusha(ls, taga[k]);
			pusha(rs, taga[k]);
			taga[k] = 0;
		}		
		if (tagb[k]) {
			pushb(ls, tagb[k]);
			pushb(rs, tagb[k]);
			tagb[k] = 0;
		}
	}
	void upd(int x, int k = 1, int l = 1, int r = n)
	{
		if (l == r) {
			ok[k] ^= 1;
			mxa[k] = mxb[k] = 0;
			return;
		}
		push_down(k);
		int mid = l + r >> 1;
		if (x <= mid) upd(x, ls, l, mid);
		else upd(x, rs, mid + 1, r);
		push_up(k);
	}
	void chkmaxa(int L, int R, int v, int k = 1, int l = 1, int r = n)
	{
        if (!ok[k]) return;
		if (L <= l && r <= R) {
			pusha(k, v);
			return;
		}
		push_down(k);
		int mid = l + r >> 1;
		if (L <= mid) chkmaxa(L, R, v, ls, l, mid);
		if (R > mid) chkmaxa(L, R, v, rs, mid + 1, r);
		push_up(k);
	}
	void chkmaxb(int L, int R, int k = 1, int l = 1, int r = n)
	{
        if (!ok[k]) return;
		if (L <= l && r <= R) {
			pushto(k);
			return;
		}
		push_down(k);
		int mid = l + r >> 1;
		if (L <= mid) chkmaxb(L, R, ls, l, mid);
		if (R > mid) chkmaxb(L, R, rs, mid + 1, r);
		push_up(k);
	}
	int query(int L, int R, int k = 1, int l = 1, int r = n)
	{
        if (!ok[k]) return 0;
		if (L <= l && r <= R) return mxb[k];
		push_down(k);
		int mid = l + r >> 1, ans = 0;
		if (L <= mid) ans = max(ans, query(L, R, ls, l, mid));
		if (R > mid) ans = max(ans, query(L, R, rs, mid + 1, r));
		return ans;
	}
}t1, t2;
bool en;
int main()
{
	freopen("doll.in", "r", stdin);
#ifdef IAKIOI
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n-------------------------" << endl;
#else
	freopen("doll.out", "w", stdout);
#endif
	io >> n >> q;
	for (int i = 1; i <= n; ++i) io >> a[i];
	for (int i = 1, j = 0; i <= n; ++i) {
		while (j < n && (a[j + 1] == 1 || t1.query(1, a[j + 1] - 1) < a[j + 1]) && (a[j + 1] == n || t2.query(1, (n - a[j + 1] + 1) - 1) < n - a[j + 1] + 1)) {
			++j;
			t1.chkmaxa(1, a[j], a[j]);
			t1.chkmaxb(a[j], n);
			t1.upd(a[j]);
			t2.chkmaxa(1, (n - a[j] + 1), (n - a[j] + 1));
			t2.chkmaxb((n - a[j] + 1), n);
			t2.upd(n - a[j] + 1);
		}
		t1.upd(a[i]);
		t2.upd(n - a[i] + 1);
		pos[i] = j;
	}
	for (int i = 1; i <= n; ++i) f[i][0] = pos[i] + 1;
    f[n + 1][0] = n + 1;
	for (int j = 1; j <= __lg(n + 1); ++j) {
		for (int i = 1; i <= n + 1; ++i) {
			f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	while (q--) {
		int l, r;
		io >> l >> r;
		int ans = r - l + 1;
		for (int i = __lg(n); i >= 0; --i) {
			if (f[l][i] <= r) {
				l = f[l][i];
				ans -= 1 << i;
			}
		}
		io << ans - 1 << '\n';
	}
	return 0;
}