#include "paint.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
const int MAXN = 1e5 + 123;
vector<int> rgoodcl[MAXN];
vector<int> go_back[MAXN];
int minimumInstructions(int n, int m, int k, vector<int> cl, vector<int> a, vector<vector<int>> goodcl) {
//reverse(goodcl.begin(), goodcl.end());
for (int i = 0; i < m; ++i) {
for (auto j : goodcl[i])
rgoodcl[j].push_back(i);
}
bitset<MAXN> ansbs;
vector<int> dfansbs(n + 1);
for (int i = 0; i < n; ++i) {
int ci = cl[i];
int t = rgoodcl[ci].size();
if (t == 0)
return -1;
if (i == 0) {
go_back[i].assign(t, 1);
continue;
}
int pci = cl[i - 1];
int pt = rgoodcl[pci].size();
go_back[i].resize(t);
if (rgoodcl[ci][0] == 0) {
if (rgoodcl[pci].back() == m - 1)
go_back[i][0] = go_back[i - 1].back() + 1;
else
go_back[i][0] = 1;
}
int pj = 0;
for (int j = 0; j < t; ++j) {
if (rgoodcl[ci][j] == 0)
continue;
while (pj < pt && rgoodcl[ci][j] - 1 > rgoodcl[pci][pj])
++pj;
if (pj < pt && rgoodcl[ci][j] - 1 == rgoodcl[pci][pj]) {
go_back[i][j] = go_back[i - 1][pj] + 1;
} else {
go_back[i][j] = 1;
}
}
int l = i + 1 - *max_element(go_back[i].begin(), go_back[i].end());
if (l + m - 1 <= i) {
++dfansbs[l];
--dfansbs[i - m + 2];
}
//cout << i << ' ' << ci << ": ";
//for (int j = 0; j < t; ++j)
//cout << "(" << rgoodcl[ci][j] << ' ' << go_back[i][j] << ") ";
//cout << endl;
}
//cout << endl;
int endcvr = 0;
int maxcvr = 0;
int ans = 0;
int remilia = 0;
for (int i = 0; i < n; ++i) {
remilia += dfansbs[i];
if (remilia)
maxcvr = i + m;
if (i >= endcvr) {
endcvr = maxcvr;
++ans;
}
if (i >= endcvr)
return -1;
}
return ans;
}
