// Problem: P7416 [USACO21FEB] No Time to Dry P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7416
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 2e5 + 5;
int pos[maxn],lst[maxn],n,m,a[maxn],f[maxn][20],lg[maxn],ans[maxn];
struct node {
	int l,r,id;
	node() {
		l = r = id = 0;
	}
	node(int l,int r,int id):l(l),r(r),id(id){}
}Q[maxn];

int RMQ(int l,int r) {
	int k = lg[r - l + 1];
	return std::min(f[l][k] , f[r - (1 << k) + 1][k]);
}

int c[maxn];

int lowbit(int x) {
	return x & -x;
}

void add(int x,int y) {
	for(;x <= n;x += lowbit(x))
		c[x] += y;
	return ;
}

int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))
		ans += c[x];
	return ans;
}

int main() {
	freopen("usaco_21Feb_dry.in","r",stdin);
	freopen("usaco_21Feb_dry.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++ i) {
		scanf("%d",&a[i]);
		lst[i] = pos[a[i]];
		pos[a[i]] = i;
		f[i][0] = a[i];
	}
	for(int i = 2;i <= n;++ i)
		lg[i] = lg[i >> 1] + 1;
	for(int k = 1;(1 << k) <= n;++ k)
		for(int i = 1;i + (1 << k) - 1 <= n;++ i)
			f[i][k] = std::min(f[i][k - 1] , f[i + (1 << (k - 1))][k - 1]);
	for(int i = 1;i <= m;++ i) {
		Q[i].id = i;
		scanf("%d %d",&Q[i].l,&Q[i].r);
	}
	std::sort(Q + 1 , Q + 1 + m , [&](const node& p,const node& q) {
		return p.r < q.r;
	});
	for(int i = 1,j = 1;i <= m;++ i) {
		for(;j <= Q[i].r;++ j) {
			add(j , 1);
			if(!lst[j])continue ;
			if(RMQ(lst[j] , j) >= a[j])
				add(lst[j] , -1);
		}
		ans[Q[i].id] = query(Q[i].r) - query(Q[i].l - 1);
	}
	for(int i = 1;i <= m;++ i)
		printf("%d\n",ans[i]);
	return 0;
}