#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
bool ok[200005];
vector <int> brr[200005], grr[200005];
int dp[200005];
int stuf[200005];
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
for(int i=0;i<M;i++){
for(auto j : B[i])brr[j].push_back(i);
}
set <int> ms;
for(int i=0;i<M;i++)stuf[i] = M;
for(int i=0;i<M-1;i++){
for(auto j : brr[C[i]])stuf[(j - i + 1000 * M) % M]--;
}
for(int i=M-1;i<N;i++){
for(auto j : brr[C[i]]){
stuf[(j - i + 1000 * M) % M]--;
int tmp = (j - i + 1000 * M)%M;
if(stuf[tmp] == 0)ms.insert(tmp);
}
int rv = i - (M - 1) - 1;
if(rv >= 0){
for(auto j : brr[C[rv]]){
stuf[(j - rv + 1000 * M) % M]++;
int tmp = (j - rv + 1000 * M) % M;
if(stuf[tmp] == 1)ms.erase(tmp);
}
}
if(!ms.empty())ok[i] = 1;
}
for(int i = 0; i < M - 1; i++)dp[i] = 2e9;
deque <pi> dq;
dq.push_back({0, -1});
for(int i=M - 1;i<N;i++){
dp[i] = 2e9;
//cout << ok[i] << ' ';
if(!dq.empty() && dq.front().se < i - M)dq.pop_front();
if(ok[i]){
int tmp= 2e9;
if(i == M - 1)tmp = 0;
for(int j = i - 1; j >= max(0, i - M); j--)tmp = min(tmp, dp[j]);
dp[i] = tmp + 1;
}
while(!dq.empty() && dq.back().fi > dp[i])dq.pop_back();
dq.push_back({dp[i], i});
}
return (dp[N - 1] > N ? -1 : dp[N - 1]);
}
