#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/int_alias.hpp"
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 7 "library2/data-structure/segmenttree.hpp"
template <class M> class SegmentTree {
public:
using size_type = int;
using value_type = typename M::value_type;
private:
size_type m_n, m_size;
std::vector<value_type> m_nodes;
public:
explicit SegmentTree(const size_type n) : m_n(n), m_size(ceil_pow2(n)) {
m_nodes.assign(m_size << 1, M::identity());
}
SegmentTree(const size_type n, const value_type v) {
*this = SegmentTree(std::vector(n, v));
}
SegmentTree(const std::vector<value_type> &s) : m_n(s.size()), m_size(ceil_pow2(s.size())) {
m_nodes.assign(m_size << 1, M::identity());
std::copy(s.begin(), s.end(), m_nodes.begin() + m_size);
for (size_type i = m_size - 1; i != 0; --i)
internal_update(i);
}
void set(size_type i, const value_type &v) {
assert(i < m_n);
i += m_size;
m_nodes[i] = v;
for (i >>= 1; i != 0; i >>= 1)
internal_update(i);
}
value_type fold() const {
return m_nodes[1];
}
value_type fold(size_type l, size_type r) const {
assert(l <= r);
assert(r <= m_n);
value_type v_l = M::identity(), v_r = M::identity();
for (l += m_size, r += m_size; l < r; l >>= 1, r >>= 1) {
if (l & 1) v_l = M::operation(v_l, m_nodes[l++]);
if (r & 1) v_r = M::operation(m_nodes[--r], v_r);
}
return M::operation(v_l, v_r);
}
value_type get(const size_type i) const {
assert(i < m_n);
return m_nodes[m_size + i];
}
template <class F> size_type max_right(size_type l, const F &f) const {
assert(l <= m_n);
assert(f(M::identity()));
if (l == m_n) return m_n;
l += m_size;
value_type sum = M::identity();
do {
while (not(l & 1))
l >>= 1;
if (not f(M::operation(sum, m_nodes[l]))) {
while (l < m_size) {
l = l << 1;
if (f(M::operation(sum, m_nodes[l]))) sum = M::operation(sum, m_nodes[l++]);
}
return l - m_size;
}
sum = M::operation(sum, m_nodes[l++]);
} while ((l & (l - 1)) != 0);
return m_n;
}
template <class F> size_type min_left(size_type r, const F &f) const {
assert(r <= m_n);
assert(f(M::identity()));
if (r == 0) return 0;
r += m_size;
value_type sum = M::identity();
do {
--r;
while (r > 1 and (r & 1))
r >>= 1;
if (not f(M::operation(m_nodes[r], sum))) {
while (r < m_size) {
r = (r << 1) | 1;
if (f(M::operation(m_nodes[r], sum))) sum = M::operation(m_nodes[r--], sum);
}
return r + 1 - m_size;
}
sum = M::operation(m_nodes[r], sum);
} while ((r & (r - 1)) != 0);
return 0;
}
private:
static constexpr size_type ceil_pow2(const size_type n_) noexcept {
size_type res = 1;
while (res < n_)
res <<= 1;
return res;
}
void internal_update(const size_type i) {
m_nodes[i] = M::operation(m_nodes[i << 1], m_nodes[i << 1 | 1]);
}
};
#line 3 "library2/utility/len.hpp"
template <class Container> int len(const Container&c){
return static_cast<int>(std::size(c));
}
#line 5 "library2/utility/lwb.hpp"
template <class Container, class T> constexpr int lwb(const Container &c, const T &val) {
return static_cast<int>(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val)));
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"
class ReversedRange {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
--itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr ReversedRange(const int f, const int l) noexcept
: first(l - 1), last(std::min(f, l) - 1) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr ReversedRange revrep(const int l, const int r) noexcept {
return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
return ReversedRange(0, n);
}
#line 8 "paper.cpp"
// #include "paint.h"
struct Monoid {
using value_type = int;
static int operation(int a, int b) {
return std::max(a, b);
}
static int identity() {
return 0;
}
};
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A,
std::vector<std::vector<int>> B) {
auto make_table = [&]() {
const int s = N - M + 1;
std::vector<std::vector<int>> likeds(K);
for (const int i : rep(M)) {
for (const int j : B[i]) {
likeds[j].push_back(i);
}
}
std::vector<bool> ret(s);
SegmentTree<Monoid> seg(M);
for (const int i : rep(M)) {
for (const int c : likeds[C[i]]) {
seg.set((c - i + M) % M, seg.get((c - i + M) % M) + 1);
}
}
if (seg.fold() == M) {
ret[0] = true;
}
for (const int i : rep(s - 1)) {
for (const int c : likeds[C[i + M]]) {
seg.set((c - i + M) % M, seg.get((c - i + M) % M) + 1);
}
for (const int c : likeds[C[i]]) {
seg.set((c - i + M) % M, seg.get((c - i + M) % M) - 1);
}
if (seg.fold() == M) {
ret[i + 1] = true;
}
}
return ret;
};
auto calc_answer = [M](std::vector<bool> d) {
const int s = len(d);
std::vector<int> r_min(s);
r_min[s - 1] = d[s - 1] ? s - 1 : s;
for (const int i : revrep(s - 1)) {
r_min[i] = d[i] ? i : r_min[i + 1];
}
if (r_min[s - 1] == s) {
return -1;
}
int answer = 1, now = s - 1;
while (now != 0) {
const int nxt = r_min[std::max(0, now - M)];
if (nxt == now) {
return -1;
}
++answer;
now = nxt;
}
return answer;
};
const auto table = make_table();
return calc_answer(table);
}
/*
int main() {
int N, M, K;
assert(3 == scanf("%d %d %d", &N, &M, &K));
std::vector<int> C(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &C[i]));
}
std::vector<int> A(M);
std::vector<std::vector<int>> B(M);
for (int i = 0; i < M; ++i) {
assert(1 == scanf("%d", &A[i]));
B[i].resize(A[i]);
for (int j = 0; j < A[i]; ++j) {
assert(1 == scanf("%d", &B[i][j]));
}
}
int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
printf("%d\n", minimum_instructions);
}
*/
