#include <bits/stdc++.h>
using namespace std;
#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >
long long n, k, rh, a[200069], sg[800069], l, r, x, mx = 1e10, ans, cn, ci, ln, cl, cr, b, q, sz, pn, rq[200069], sp[200069], pq, pv, cv, lz[800069], ca;
vector<long long> pos[200069];
vector<pair<long long, long long> > vc;
void prop(long long v, long long sl, long long sr) {
if (lz[v] != 0) {
sg[v] += lz[v];
sg[v] = min(sg[v], mx);
if (sl != sr) {
lz[2*v] += lz[v];
lz[2*v+1] += lz[v];
}
lz[v] = 0;
}
}
void upd(long long v, long long sl, long long sr) {
if (l>r) {
return;
}
prop(v, sl, sr);
if (sl>r || sr<l) {
return;
}
if (sl>=l && sr<=r) {
lz[v] += x;
prop(v, sl, sr);
return;
}
long long md = (sl+sr)/2;
upd(2*v, sl, md);
upd(2*v+1, md+1, sr);
sg[v] = max(sg[2*v], sg[2*v+1]);
sg[v] = min(sg[v], mx);
}
long long qr(long long v, long long sl, long long sr) {
if (l>r) {
return 0;
}
prop(v, sl, sr);
if (sl>r | sr<l) {
return 0;
}
if (sl>=l && sr<=r) {
return sg[v];
}
long long md = (sl+sr)/2, cn, nn1, nn2;
nn1 = qr(2*v, sl, md);
nn2 = qr(2*v, md+1, sr);
cn = max(nn1, nn2);
cn = min(cn, mx);
return cn;
}
int main() {
nyahalo
long long i, j;
ans = mx;
cin >> n >> k >> rh;
for (i=1; i<=k; i++) {
rq[i] = 0;
}
for (i=1; i<=n; i++) {
cin >> a[i];
pos[a[i]].push_back(i);
}
for (i=1; i<=rh; i++) {
cin >> b >> q;
vc.push_back(make_pair(b, q));
rq[b] = q;
}
sort(vc.begin(), vc.end());
sz = vc.size();
for (i=0; i<sz; i++) {
l = i+1;
r = i+1;
b = vc[i].first;
q = vc[i].second;
if (pos[b].size()<q) {
x = mx;
} else {
cl = pos[b][0];
cr = pos[b][q-1];
x = cr;
}
sp[b] = i+1;
upd(1, 1, sz);
}
for (i=1; i<=n; i++) {
if (i == 1) {
l = 1;
r = sz;
ca = qr(1, 1, sz);
//cout << "ca: " << ca << "\n";
ans = min(ans, ca);
continue;
}
pn = a[i-1];
pq = rq[pn];
if (pq>0) {
//cout << "i: " << i << "\n";
cl = lower_bound(pos[pn].begin(), pos[pn].end(), i-1)-pos[pn].begin();
cr = cl+pq-1;
//cout << "cl: " << cl << " cr: " << cr << "\n";
if (cr>=pos[pn].size()) {
x = mx;
} else {
pv = pos[pn][cr]-pos[pn][cl]+1;
cl++;
cr++;
if (cr>=pos[pn].size()) {
cv = mx+pv;
} else {
cv = pos[pn][cr]-i+1;
}
x = cv-pv;
}
ci = sp[pn];
l = ci;
r = ci;
upd(1, 1, sz);
l = 1;
r = ci-1;
x = -1;
upd(1, 1, sz);
l = ci+1;
r = sz;
x = -1;
upd(1, 1, sz);
} else {
l = 1;
r = sz;
x = -1;
upd(1, 1, sz);
}
l = 1;
r = sz;
//cout << "ca: " << ca << "\n";
ca = qr(1, 1, sz);
ans = min(ans, ca);
}
if (ans>1e9) {
cout << "impossible\n";
} else {
cout << ans << "\n";
}
otsumiko
}
