#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
vector <vector <int>> likers;
vector <int> pos;
vector <vector <int>> spreadLeft;
deque <int> dq;
vector <int> dp;
/**
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4
*/
int minimumInstructions(int N,int M,int K,vector <int> C,vector <int> A,vector <vector <int>> B)
{
likers.resize(K);
for(int i=0; i<M; i++)
for(auto it:B[i])
likers[it].push_back(i);
pos.resize(M);
for(int i=0; i<M; i++)
pos[i]=-1;
dp.resize(N);
spreadLeft.resize(N);
for(int i=0; i<N; i++)
{
spreadLeft[i].resize(likers[C[i]].size());
int maxim;
if(i>0)
{
maxim=0;
for(int j=0; j<(int)likers[C[i]].size(); j++)
{
int pj=pos[(likers[C[i]][j]-1+M)%M];
if(pj==-1)
spreadLeft[i][j]=1;
else
spreadLeft[i][j]=spreadLeft[i-1][pj]+1;
maxim=max(maxim,spreadLeft[i][j]);
}
}
else
{
maxim=1;
for(int j=0; j<(int)likers[C[i]].size(); j++)
spreadLeft[i][j]=1;
}
if(i>0)
{
for(int j=0; j<(int)likers[C[i-1]].size(); j++)
pos[likers[C[i-1]][j]]=-1;
}
for(int j=0; j<(int)likers[C[i]].size(); j++)
pos[likers[C[i]][j]]=j;
if(i<M-1)
dp[i]=N+1;
else if(i==M-1)
{
if(maxim<M)
return -1;
dp[i]=1;
}
else
{
while(!dq.empty() && dq.front()<i-M)
dq.pop_front();
if(maxim>=M)
dp[i]=min(N+1,dp[dq.front()]+1);
else
dp[i]=N+1;
}
while(!dq.empty() && dp[dq.back()]>=dp[i])
dq.pop_back();
dq.push_back(i);
}
if(dp[N-1]==N+1)
return -1;
return dp[N-1];
}
