#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll base = 1<<18; ll inf = 1e18; vector<pair<ll, ll>> T(2*base,{0,0}); vector<ll> lazy(2*base,0); void push(ll v, ll l, ll r) { if(!lazy[v] || v>=base) return; for(auto x : {l,r}) { T[x].first += lazy[v]; lazy[x] += lazy[v]; } lazy[v] = 0; } void update(ll v, ll a, ll b, ll p, ll k, ll val) { if(b < p || k < a) return; if(p<=a&&b<=k) { T[v].first += val; lazy[v] += val; return; } ll l=2*v; ll r=2*v+1; ll mid = (a+b)/2; push(v,l,r); update(l,a,mid,p,k,val); update(r,mid+1,b,p,k,val); T[v] = max(T[l], T[r]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,k,r; cin >> n >> k >> r; vector<ll> reqs(k); vector<ll> a(n); for(ll i=0; i<n; ++i) cin >> a[i]; while(r--) { ll b, q; cin >> b >> q; reqs[b] = q; } vector<vector<int>> pos(k); vector<int> idx(n+1), cnt(k, 1); for(int i=0; i<k; ++i) pos[i].push_back({0}); for(int i=0; i<n; ++i) { pos[a[i]].push_back(i+1); idx[i+1] = cnt[a[i]]++; } for(ll i=0; i<base; ++i) { T[i+base].second = i; } for(ll i=base-1; i>=1; --i) { T[i] = max(T[i+i], T[i+i+1]); } for(int i=0; i<k; ++i) if(reqs[i]==0) update(1,0,base-1,0,base-1,1); ll best = -inf; ll ans = inf; for(int i=1; i<=n; ++i) { int c = a[i-1]; if(reqs[c]==0) continue; if(cnt[i] >= reqs[c]) { update(1,0,base-1,pos[c][idx[i]-reqs[c]],pos[c][idx[i]-reqs[c]+1]-1,1); } while(T[1].first==k) { best = max(best,T[1].second); update(1,0,base-1,T[1].second,T[1].second,-inf); } ans = min(ans, i-best); } if(ans==inf) cout << "impossible\n"; else cout << ans << "\n"; return 0; }