P4792 [BalticOI 2018] Martian DNA

**This problem is translated from [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day 1 “[Martian DNA](https://boi18-day1-open.kattis.com/problems/boi18.dna)”.** You are given a string of length $N$ over an alphabet of size $|\Sigma| = K$, and $R$ requirements. Each requirement is: in the substring, character $B$ must appear at least $Q$ times. Find the length of the shortest substring that satisfies all requirements.

The first line contains three integers $N,\, K,\, R$, representing the length of the string, the size of the alphabet, and the number of requirements. It is guaranteed that $1\leqslant R\leqslant K\leqslant N$. The second line contains $N$ space-separated integers describing the string. Characters are numbered starting from $0$, and every character in the alphabet appears at least once. The next $R$ lines each contain two integers $B$ and $Q$, describing one requirement. It is guaranteed that $0\leqslant B < K,\, 1\leqslant Q\leqslant N$, and no character will be required more than once.

Output one integer: the length of the shortest substring that satisfies all requirements. In particular, if no such substring exists, output "``impossible``".

#### Explanation for Sample 1 There are three substrings of length $2$ that contain one occurrence each of characters $0$ and $1$: ``0 1``, ``1 0``, and ``0 1``. However, there is no substring of length $1$ that satisfies the requirements, so the shortest valid substring has length $2$. #### Explanation for Sample 2 The shortest substring that satisfies the requirements is ``1 3 2 0 1 2 0``. #### Explanation for Sample 3 In this string, the number of ``0`` is not enough. | Subtask | Score | Constraints | |:--------:|:------:|:------:| |$1$ |$16$ |$1\leqslant N\leqslant 100,\, R\leqslant 10$| |$2$ |$24$ |$1\leqslant N\leqslant 4\, 000,\, R\leqslant 10$| |$3$ |$28$ |$1\leqslant N\leqslant 200\, 000,\, R\leqslant 10$| |$4$ |$32$ |$1\leqslant N\leqslant 200\, 000$| Thanks to Hatsune_Miku for providing the translation. Translated by ChatGPT 5