#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> arr;
int get_mex(int l, int r) {
int mex = 1;
vector<bool> ok(n+2, false);
for (int i = l; i <= r; i++) {
ok[arr[i]] = true;
while (ok[mex]) mex++;
}
return mex;
}
vector<int> solve(int N, vector<int>& v, int Q, vector<pair<int,int>>& queries)
{
n = N;
q = Q;
arr = v;
vector<int> ans;
for (auto [l, r]: queries) {
int targ = get_mex(l, r);
vector<bool> ok(n+2, false);
int k = 0, currMex = 1;
for (int i = l; i <= r; i++) {
ok[arr[i]] = true;
while (ok[currMex]) currMex++;
if (currMex == targ) {
k++;
for (int j = 1; j <= currMex; j++) {
ok[j] = false;
}
currMex = 1;
}
}
ans.push_back(k);
}
return ans;
}
/*
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n,q;
std::cin>>n>>q;
std::vector<int> vec;
for(int i=0;i<n;i++)
{
int x;
std::cin>>x;
vec.push_back(x);
}
std::vector<std::pair<int,int>> queries;
for(int i=0;i<q;i++)
{
int l,r;
std::cin>>l>>r;
queries.push_back(std::make_pair(l,r));
}
std::vector<int> res=solve(n,vec,q,queries);
for(int i=0;i<q;i++)
std::cout<<res[i]<<'\n';
return 0;
}
*/
