#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>
using namespace std;
const int INF = 1e9 + 7;
const int maxn = 5e5 + 7;
int n , q , st[maxn*4] , ans[maxn] , a[maxn];
void update(int id , int l , int r , int pos , int val)
{
if(l > pos || r < pos) return;
if(l == r)
{
st[id] = val; return;
}
int mid = (l+r)/2;
update(id*2 , l , mid , pos , val);
update(id*2+1 , mid+1 , r , pos, val);
st[id] = st[id*2] + st[id*2+1];
}
int getsum(int id , int l , int r , int u , int v)
{
if(r < u || l > v) return 0;
if(u <= l && r <= v) return st[id];
int mid = (l+r)/2;
return (getsum(id*2 , l , mid , u , v) + getsum(id*2+1 , mid+1 , r , u , v));
}
void compress()
{
vector <int> val;
for(int i = 1; i <= n; i++) val.push_back(a[i]);
sort(val.begin() , val.end());
for(int i = 1; i <= n; i++)
{
a[i] = upper_bound(val.begin() , val.end() , a[i]) - val.begin();
}
}
vector <int> pos[maxn];
vector <pii> query[maxn];
void solve()
{
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
compress();
for(int i = 1; i <= q; i++)
{
int l , r; cin >> l >> r;
query[r].push_back({l , i});
}
for(int i = 1; i <= n; i++)
{
pos[a[i]].push_back(i);
int sz = pos[a[i]].size();
if(sz >= 2) update(1 , 1 , n , pos[a[i]][sz-2] , 1);
if(sz >= 3) update(1 , 1 , n , pos[a[i]][sz-3] , -1);
if(sz >= 4) update(1 , 1 , n , pos[a[i]][sz-4] , 0);
for(pii tmp: query[i])
{
int j = tmp.fi;
int id = tmp.se;
ans[id] = getsum(1 , 1 , n , j , i);
}
}
for(int i = 1; i <= q; i++) {cout << ans[i] << '\n';}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
