using ll = long long;

void solve() {
   int n, m, t;
   cin >> n >> m >> t;
   vector<vector<int>> a(n, vector<int>(m));
   vector<tuple<int, ll, int>> tp; 
   for (int i = 0; i < n; i++) {
      for (int k = 0; k < m; k++) {
         cin >> a[i][k];
      }
      sort(a[i].begin(), a[i].end());
      int cnt = 0;
      int sum = 0;
      ll pen = 0;
      for (int k = 0; k < m; k++) {
         if (sum + a[i][k] <= t) {
            sum += a[i][k];
            pen += sum; 
            cnt += 1;
         } else {
            break;
         }
      }
      tp.emplace_back(cnt, pen, i);
   }
   sort(tp.begin(), tp.end(), [&](tuple<int, ll, int> a, tuple<int, ll, int> b) {
      if (get<0>(a) == get<0>(b)) {
         return get<1>(a) < get<1>(b);
      } 
      return get<0>(a) > get<0>(b);
   });
   int ans = 0;
   for (int i = 0; i < n; i++) {
      if (get<2>(tp[i]) == 0) {
         ans = i + 1;
         break;
      }
   }
   cout << ans << "\n";
}

class Solution {
public:
    int minExtraChar(string s, vector<string>& d) {
        int n = s.size();
        vector<int> f(n + 1);
        for (int i = 0; i < n; i++) {
            string t; 
            for (int k = i; k < n; k++) {
                t += s[k];
                for (int r = 0; r < d.size(); r++) {
                    if (t == d[r]) {
                        f[i]++, f[k + 1]--;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            f[i + 1] += f[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == 0) ans += 1;
        }
        return ans;
    }
};

s = "kevlplxozaizdhxoimmraiakbak",
d = ["yv","bmab","hv","bnsll","mra","jjqf","g","aiyzi","ip","pfctr","flr","ybbcl","biu","ke","lpl","iak","pirua","ilhqd","zdhx","fux","xaw","pdfvt","xf","t","wq","r","cgmud","aokas","xv","jf","cyys","wcaz","rvegf","ysg","xo","uwb","lw","okgk","vbmi","v","mvo","fxyx","ad","e"],
Expected Answer: 9, 
My output: 8

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector<vector<int>> g(2001);
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        a[i].first = u + 1000;
        a[i].second = v + 1000;
        g[u + 1000].push_back(v + 1000);
        g[v + 1000].push_back(u + 1000);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i].first;
        int y = a[i].second;
        bool l = 0, r = 0, u = 0, d = 0;
        for (auto k : g[y]) {
            if (k > x) {
                r = 1;
            } else if (k < x) {
                l = 1;
            }       
        }
        for (auto k : g[x]) {
            if (k > y) {
                u = 1;
            } else if (k < y) {
                d = 1;
            }
        }
        if (l == 1 and r == 1 and u == 1 and d == 1) {
            ans += 1;
        }
    }
    std::cout << ans << "\n";
    return 0;
}

void solve() {
    int n, x, q;
    cin >> n >> x >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= i;
    }
    map<int, int> f;
    for (int i = 0; i < x; i++) {
        f[a[i]]++;
    }
    multiset<int, greater<int>> mt;
    for (auto it : f) {
        mt.insert(it.second);
    }
    vector<int> ans(n - x + 1);
    ans[0] = x - *mt.begin();
    for (int i = x; i < n; i++) {
        int cur = i;
        int beg = i - x;
        mt.erase(mt.find(f[a[beg]]));
        f[a[beg]]--;
        mt.insert(f[a[beg]]);
        mt.erase(mt.find(f[a[cur]]));
        f[a[cur]]++;
        mt.insert(f[a[cur]]);
        ans[beg] = x - *mt.begin();
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ans[l - 1] << "\n";
    }
}

    multiset<int, greater<int>> mt;
    for(int i = 1; i <= n; i++) {
        mt.insert(0);
    }