#include #include #include using namespace std; using namespace __gnu_pbds; #define int long long int template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; #define ld long double #define nl cout << "\n"; #define getunique(v) \ { \ sort(v.begin(), v.end()); \ v.erase(unique(v.begin(), v.end()), v.end()); \ } #define forn(a, b) for (int i = a; i < b; i++) #define __builtin_popcountll __builtin_popcountll #define __builtin_clzll __builtin_clzll #define __builtin_ctzll __builtin_ctzll #define yesno(b) cout << ((b) ? "YES" : "NO"); #define pii pair #define mp(a, b) make_pair(a, b) #define pb push_back #define all(a) a.begin(), a.end() #define vi vector #define hhh cout << "here" << endl; #define mod1 1000000007 #define mod2 998244353 const int inf = 1e17 + 1; #define FL(i, a, n) for (int i = a; i < n; i++) #define FR(i, a, n) for (int i = a; i >= n; i--) class segmentTree { private: struct item { int v; }; int size; vector store; item NEUTRAL_ELEMENT = {0ll}; item merge(item a, item b) { return {a.v + b.v}; } item single(int v) { return {v}; } void set_point(int i, int v, int x, int lx, int rx) { if (rx - lx == 1) { store[x] = single(v); return; } int mid = (lx + rx) / 2; if (i < mid) set_point(i, v, 2 * x + 1, lx, mid); else set_point(i, v, 2 * x + 2, mid, rx); store[x] = merge(store[2 * x + 1], store[2 * x + 2]); } void build(vector &a, int x, int lx, int rx) { if (rx - lx == 1) { if (lx < (int)a.size()) store[x] = single(a[lx]); return; } int mid = (lx + rx) / 2; build(a, 2 * x + 1, lx, mid); build(a, 2 * x + 2, mid, rx); store[x] = merge(store[2 * x + 1], store[2 * x + 2]); } item get_range(int l, int r, int x, int lx, int rx) { if (l >= rx || r <= lx) return NEUTRAL_ELEMENT; if (lx >= l && rx <= r) return store[x]; int mid = (lx + rx) / 2; item left = get_range(l, r, 2 * x + 1, lx, mid); item right = get_range(l, r, 2 * x + 2, mid, rx); return merge(left, right); } public: segmentTree() : size(0) {} void init(int n) { size = 1; while (size < n) size <<= 1; store.assign(2 * size, NEUTRAL_ELEMENT); } void build(vector &a) { build(a, 0, 0, size); } // inclusive [l, r] query item get(int l, int r) { if (l > r) return NEUTRAL_ELEMENT; return get_range(l, r + 1, 0, 0, size); } void set(int i, int v) { set_point(i, v, 0, 0, size); } }; void solve() { int n; cin >> n; vector a(n); forn(0, n) cin >> a[i].first >> a[i].second; int m; cin >> m; vector h(m); forn(0, m) cin >> h[i].first >> h[i].second; vi temp; forn(0, n) temp.pb(a[i].first); forn(0, m) temp.pb(h[i].first); map compress; sort(all(temp)); int x = 0; for (auto it : temp) { if (compress.count(it)) continue; compress[it] = x++; } int sz = compress.size(); forn(0, n) a[i].first = compress[a[i].first]; forn(0, m) h[i].first = compress[h[i].first]; segmentTree st; st.init(sz + 1); forn(0, sz) st.set(i, 0); forn(0, n) { int j = a[i].first; st.set(j, st.get(j, j).v + 1); } map store; forn(0, n) { store[a[i].second].pb(a[i].first); } for (auto &it : store) { sort(all(it.second)); } forn(0, m) { int strength = h[i].first; int type = h[i].second; int ans = st.get(0, strength).v; int l = 0, r = store[type].size(); if (store[type].empty()) { cout << ans; nl; continue; } if (store[type][0] > strength) { cout << ans; nl; continue; } while (r > l + 1) { int mid = (l + r) / 2; if (store[type][mid] > strength) r = mid; else l = mid; } ans -= r; cout << ans; nl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int t = 1; // cin >> t; while (t--) { solve(); // nl; } return 0; }