#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;

const int MAXN = 2e5 + 10;
const int MAXQ = 2e5 + 10;
const int MAXV = 2e5 + 10;
const int LEN = 447;

struct QUESTION {
	int l, r, id;
} ques[MAXQ];

bool cmp(QUESTION x, QUESTION y) {
	if (x.l / LEN < y.l / LEN) return x.l / LEN < y.l / LEN;
	return x.r / LEN < y.r / LEN;
}

int n, Q;
int a[MAXN], t[MAXV], ncolor, nup;
int ans[MAXQ];

void delfromleft(int nl) {
	t[a[nl]]--;
	if (t[a[nl]] == 0) ncolor--;
	if (a[nl] < a[nl + 1]) nup--;
}

void addfromleft(int nl) {
	t[a[nl]]++;
	if (t[a[nl]] == 1) ncolor++;
	if (a[nl] < a[nl + 1]) nup++;
}

void addfromright(int nr) {
	t[a[nr]]++;
	if (t[a[nr]] == 1) ncolor++;
	if (a[nr - 1] < a[nr]) nup++;
}

void delfromright(int nr) {
	t[a[nr]]--;
	if (t[a[nr]] == 0) ncolor--;
	if (a[nr - 1] < a[nr]) nup--;
}

int main() {
	freopen("dry.in", "r", stdin);
	freopen("dry.out", "w", stdout);
	scanf("%d %d", &n, &Q);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= Q; ++i) {
		scanf("%d %d", &ques[i].l, &ques[i].r);
		ques[i].id = i;
	}
	
	sort(ques + 1, ques + Q + 1, cmp);
	int nl = 1, nr = 0;
	for (int i = 1; i <= Q; ++i) {
		while (nl < ques[i].l) delfromleft(nl++);
		while (nl > ques[i].l) addfromleft(--nl);
		while (nr < ques[i].r) addfromright(++nr);
		while (nr > ques[i].r) delfromright(nr--);
		ans[ques[i].id] = max(nup, ncolor);
	}
	
	for (int i = 1; i <= Q; ++i) {
		printf("%d\n", ans[i]);
	}
	return 0;
}