#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 5e5+15;
const int INF = 1e9+10;
const int LOG = 19;
const int MOD = 1e9+7;
int n, m, k;
int c[MAXN], a[MAXN];
vector <int> have[MAXN];
int dp[MAXN], cnt[MAXN], numcan;
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
n = N; m = M; k = K;
int te = (n+m-1)/m * m;
for(int i=1; i<=n; i++) c[i] = C[i-1];
for(int i=1; i<=m; i++){
a[i] = A[i-1];
for(auto in : B[i-1]) have[in].pb(i);
}
dp[0] = 0;
for(int i=1; i<=n; i++) dp[i] = INF;
for(int i=1; i<=m-1; i++){
int val = c[i];
for(auto in : have[val]){
int idx = (in-i+te+m)%m;
cnt[idx]++;
}
}
multiset <int> mu;
for(int i=0; i<=m-1; i++) mu.insert(dp[i]);
for(int i=m; i<=n; i++){
int val = c[i];
for(auto in : have[val]){
int idx = (in-i+te+m)%m;
cnt[idx]++;
if(cnt[idx] == m) numcan++;
}
if(i != m){
val = c[i-m];
for(auto in : have[val]){
int idx = (in-i+te+m)%m;
cnt[idx]--;
if(cnt[idx] == m-1) numcan--;
}
}
if(i-m-1 >= 0) mu.erase(mu.find(dp[i-m-1]));
if(!mu.empty() && numcan != 0) dp[i] = (*mu.begin())+1;
mu.insert(dp[i]);
// cout << i << ' ' << numcan << ' ' << dp[i] << " umcan\n";
}
return (dp[n]>n ? -1 : dp[n]);
}
