#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll,ll> prll;
#define fi first
#define se second
#define sz size
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) ((x).begin()), ((x).end())
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)
inline void maxa (ll &a, ll b) { if (a<b) a=b; }
inline void mina (ll &a, ll b) { if (a>b) a=b; }
#define mxN (100'010ll)
#define mxM (50'010ll)
#define mxK (100'010ll)
#define INF (LLONG_MAX>>3ll)
ll n, m, k;
vcll ar(mxN);
vc<vc<int>> B;
vc<vcll> cl_needs(mxN);
vc<vcll> pl_needs(mxN);
vcll temp_fr(mxK,0);
vc<vcll> inds(mxK);
inline void clean_dups (vcll &a)
{
for (ll c:a) temp_fr[c]=1;
vcll b;
for (ll c:a) if (temp_fr[c])
{
b.pb(c);
temp_fr[c]=0;
}
}
inline ll modit (ll x) { return ((x%m)+m)%m; }
inline void bd_needs()
{
ll j, c;
f0r(j,0,m-1) for (int c:B[j]) cl_needs[c].pb(j+1);
f0r(c,0,k)
{
for (ll i:inds[c])
{
for ( ll J:cl_needs[c])
{
pl_needs[i].pb(modit(J-i));
// printf("pl %lli, needs %lli\n", i, modit(J-i));
}
clean_dups(pl_needs[i]);
}
cl_needs[c].clear();
}
}
vcll fr(mxK,0);
ll good_cnt;
inline void push (ll i)
{
for (ll r:pl_needs[i])
if (++fr[r]==m) good_cnt++;
}
inline void pull (ll i)
{
for (ll r:pl_needs[i])
if (fr[r]--==m) good_cnt--;
}
vcb can_paint(mxN,0);
vcll dp(mxN,INF);
inline void slide()
{
ll i, j;
good_cnt=0;
f0r(i,1,m) push(i);
can_paint[m]=good_cnt;
f0r(i,m+1,n)
{
push(i);
pull(i-m);
can_paint[i]=good_cnt;
}
// f0r(i,1,n) printf("can_paint[%lli]: %lli\n", i, (ll)can_paint[i]);
}
struct MINQ
{
ll push_time, pop_time;
deque<prll> q;
inline MINQ()
{
push_time=0;
pop_time=0;
while (q.sz()) q.ppb();
q.pb({INF,0});
}
inline void push (ll x)
{
while (q.sz() and x<q.back().fi) q.ppb();
q.pb({x,++push_time});
// printf("pushed {%lli, %lli}\n", x, push_time);
}
inline void pop () { if (q.sz() and q.front().se == ++pop_time)
{
// printf("popping {%lli, %lli}\n", q.front().fi, q.front().se);
q.ppf();
}
}
inline ll min() { return q.sz() ? q.front().fi : INF; }
} minq;
inline void do_dp()
{
dp[0]=0;
ll i;
f0r(i,0,m-1) minq.push(dp[i]);
// printf("dp[1]: %lli\n", dp[1]);
f0r(i,m,n)
{
/*
printf("i: %lli\n", i);
if (can_paint[i])
{
printf("%lli is good, minq.min(): %lli\n", i, minq.min());
}
*/
dp[i] = can_paint[i] ? minq.min()+1 : INF;
minq.push(dp[i]);
// printf("pushinggggggggggggggg\n");
minq.pop();
// printf("poppinnnnnnnnnnnnnnn\n");
}
// f0r(i,1,n) printf("dp[%lli]: %lli\n", i, dp[i]);
}
inline void bd_inds()
{
ll i;
f0r(i,1,n) inds[ar[i]].pb(i);
}
int minimumInstructions( int N, int M, int K, vc<int> C, vc<int> A, vc<vc<int>> bar)
{
n=N; m=M; k=K;
swap(B,bar);
ll i, j;
f0r(i,1,n) ar[i]=C[i-1];
// printf("got input\n");
bd_inds();
bd_needs();
// printf("bt needs\n");
slide();
// printf("slided\n");
do_dp();
// printf("done\n");
// printf("n: %lli, dp[n]: %lli\n", n, dp[n]);
return dp[n]>=n+10 ? -1 : dp[n];
}
