#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6, inf = 0x3f3f3f3f; 
int n, a[N], q, mx[N], cnt[N]; 
vector <int> td; 

void solve () {
	cin >> n >> q; 
	for (int i = 1;i <= n;i++) cin >> a[i]; 
	while (q--) {
		int l, r; cin >> l >> r;
		mx[r+1] = -inf; 
		td.clear(); 
		for (int i = l;i <= r;i++) td.pb(a[i]), cnt[a[i]] = 0;  
		sort(td.begin(), td.end(), [&](int x, int y) { return x > y; }); 
		for (int i = r;i >= l;i--) mx[i] = max(mx[i+1], a[i]); 
		int mn = inf, c = 0; 
		for (int i = l;i <= r;i++) {
			++cnt[a[i]]; 
			mn = min(mn, a[i]); if ((cnt[a[i]] > 1 && a[i] >= td[i-l])|| mn >= mx[i+1]) ++c; 
		}
		cout << r-l+1-c << "\n"; 
	}
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1; 
	while (T--) solve();
	return 0;
}