#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define pli pair<ll, int> #define debug(x) cout << #x << " = " << x << '\n' #define all(a) a.begin(), a.end() #define SZ(a) (int)(a).size() const int N = 2e5 + 5; const int mod = 1e9 + 7; const ll inf64 = 3e18; const int inf32 = 2e9 + 5; struct FenwickTree { const static int LG = 18; int n; vector<int> node; FenwickTree() {} FenwickTree(int n) : n(n), node(n + 3, 0) {} void upd(int i, int x) { for(; i <= n; i += i & (-i)) node[i] += x; } int get(int i) { int res = 0; for(; i; i -= i & (-i)) res += node[i]; return res; } int get(int l, int r) { return (l <= r ? get(r) - get(l - 1) : 0); } int walk() { int pos = 0; for(int i = LG - 1; i >= 0; i--) { if(pos + (1 << i) < n && node[pos + (1 << i)] == 0) pos += (1 << i); } return pos + 1; } }; int n, k, m, a[N]; vector<int> pos[N]; int req[N]; void solve() { cin >> n >> k >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; pos[a[i]].push_back(i); } for(int i = 1, x, y; i <= m; i++) { cin >> x >> y; req[x] = y; } int ans = n + 1; FenwickTree fen(n); for(int i = 1; i <= n; i++) { if(req[a[i]]) { int it = lower_bound(all(pos[a[i]]), i) - pos[a[i]].begin(); if(it - req[a[i]] + 1 >= 0) { it += 1 - req[a[i]]; fen.upd(pos[a[i]][it], 1); if(it > 0) fen.upd(pos[a[i]][it - 1], -1); } } int l = fen.walk(); if(fen.get(l, i) == m) ans = min(ans, i - l + 1); } if(ans > n) cout << "impossible"; else cout << ans << '\n'; } int main() { auto start = chrono::steady_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } int test = 1; // cin >> test; while(test--) solve(); chrono::duration<double> elapsed {chrono::steady_clock::now() - start}; cerr << "\n>> Runtime: " << elapsed.count() << "s\n"; }

dna.cpp: In function 'int main()':
dna.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~