Martian DNA

As you may know, human DNA can be written as a long string over a four-letter alphabet (A, C, G, T, standing for adenine, cytosine, guanine, and thymine).

Martian DNA is different. A recent survey found that Martian DNA consists of no fewer than K distinct nucleobases, so it can be written as a string over an alphabet of size K.

A research team that wants to use Martian DNA in artificial intelligence applications has asked for one contiguous piece of a Martian DNA string as a sample. For R of the nucleobases, the team requires that at least a given quantity of that nucleobase appear in the sample.

Find the length of the shortest contiguous substring of the DNA that satisfies all of the team's requirements.

The first line contains three integers N, K, and R: the total length of the Martian DNA, the alphabet size, and the number of nucleobases carrying a minimum-quantity requirement, with $1 \le R \le K \le N$.

The second line contains N space-separated integers describing the whole Martian DNA string. The i-th integer $D_i$ is the nucleobase at position i of the string, numbered from zero so that $0 \le D_i < K$. Every nucleobase occurs at least once in the string.

Each of the following R lines contains two integers B and Q: a nucleobase and its minimum required quantity ($0 \le B < K$, $1 \le Q \le N$). No nucleobase appears more than once among these R lines.

Print a single integer: the length of the shortest contiguous substring of the DNA that meets all of the requirements. If no such substring exists, print impossible.

Expand the right end step by step while shrinking the left end as far as possible. Counting how many of each required nucleobase the current window holds, and tracking how many kinds have reached their quotas, finds the optimum in a single pass over the DNA.