#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "paint.h"
llo dp[100001];
llo co[100001];
llo val[100001];
vector<llo> xx[100001];
//multiset<llo> cur;
llo cot=0;
int minimumInstructions( int n, int m, int k,vector<int> it,vector<int> aa,vector<vector<int>> bb) {
for(llo i=0;i<m;i++){
for(auto j:bb[i]){
xx[j].pb(i);
// cout<<j<<":"<<i<<endl;
}
}
/*for(llo i=0;i<m;i++){
cur.insert(0);
}*/
for(llo i=0;i<n;i++){
for(auto j:xx[it[i]]){
llo ac=(j-i+(llo)n*m)%m;
/*auto jj=cur.find(co[ac]);
cur.erase(jj);*/
if(co[ac]==m){
cot-=1;
}
co[ac]+=1;
if(co[ac]==m){
cot+=1;
}
/*cur.insert(co[ac]);*/
}
if(i>=m){
for(auto j:xx[it[i-m]]){
llo ac=(j-i+(llo)n*m)%m;
if(co[ac]==m){
cot-=1;
}
co[ac]-=1;
if(co[ac]==m){
cot+=1;
}
}
}
if(cot>0){
val[i]=1;
// cout<<i<<endl;
}
}
deque<pair<int,int>> xx;
for(int i=m-1;i<n;i++){
if(val[i]==0){
dp[i]=n+1;
continue;
}
while(xx.size()){
if(xx.front().b<i-m){
xx.pop_front();
continue;
}
break;
}
if(i==m-1){
dp[i]=1;
}
else{
if(xx.size()==0){
dp[i]=n+1;
continue;
}
dp[i]=xx.front().a+1;
}
while(xx.size()){
if(xx.back().a>=dp[i]){
xx.pop_back();
continue;
}
break;
}
xx.pb({dp[i],i});
}
if(dp[n-1]>n){
return -1;
}
return dp[n-1];
return 0;
}
