#include <bits/stdc++.h> #define ll long long #define ld long double #define pii pair<int,int> #define pll pair<long long,long long> #define vi vector<int> #define vl vector<long long> #define ff first #define ss second #define rep(i,n) for(int i = 0; i < n; i++) #define rep2(i,a,b) for(int i = a; i <= b; i++) #define forall(it,x) for(auto it: x) #define pb push_back #define all(x) x.begin(),x.end() #define siz(x) (int)x.size(); #define count_bits(x) __builtin_popcount(x) using namespace std; const ll MOD = 998244353; const int n = 2500; pii jump_up[2501][2501]; pii jump_down[2501][2501]; pll jump_val_up[2501][2501]; pll jump_val_down[2501][2501]; bool spc[2502][2502]; int min_y[2502][2502]; int min_x[2502][2502]; int max_y[2502][2502]; int max_x[2502][2502]; int pref[2502][2502]; ll ans[2502][2502]; int get_sum(int y1, int y2, int x1, int x2) { if(y1 > y2 || x1 > x2) return 0; return pref[y2][x2]-pref[y2][x1-1]-pref[y1-1][x2]+pref[y1-1][x1-1]; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int m; cin >> m; vector<pii> points; rep(i,m) { int x,y; cin >> x >> y; spc[x][y] = 1; points.pb({x,y}); } rep2(i,1,n+1) rep2(j,1,n+1) pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1] + (spc[i][j] == 1); rep2(i,0,n+1) rep2(j,0,n+1) { min_y[i][j] = 1e9; min_x[i][j] = 1e9; } rep2(i,1,n) rep2(j,1,n) { min_y[i][j] = min({min_y[i-1][j],min_y[i][j-1],(spc[i][j] ? i : (int)1e9)}); min_x[i][j] = min({min_x[i-1][j],min_x[i][j-1],(spc[i][j] ? j : (int)1e9)}); } for(int i = n; i >= 1; i--) for(int j = n; j >= 1; j--) { max_y[i][j] = max({max_y[i+1][j],max_y[i][j+1],(spc[i][j] ? i : (int)-1)}); max_x[i][j] = max({max_x[i+1][j],max_x[i][j+1],(spc[i][j] ? j : (int)-1)}); } rep2(i,1,n) rep2(j,1,n) { // up int nxt_y = min(i,min_y[i-1][j-1]); int nxt_x = max(j,max_x[i+1][j+1]); jump_up[i][j] = {nxt_y,nxt_x}; // down nxt_y = max(i,max_y[i+1][j+1]); nxt_x = min(j,min_x[i-1][j-1]); jump_down[i][j] = {nxt_y,nxt_x}; } rep2(i,1,n) for(int j = n; j >= 1; j--) { pii nxt = jump_up[i][j]; if(nxt.ff == i && nxt.ss == j) { jump_val_up[i][j] = {spc[i][j],0}; continue; } jump_val_up[i][j] = jump_val_up[nxt.ff][nxt.ss]; jump_val_up[i][j].ff += jump_val_up[i][j].ss; ll new_elms = get_sum(1,i,j,nxt.ss-1)+get_sum(nxt.ff+1,i,nxt.ss,n); jump_val_up[i][j].ff += new_elms; jump_val_up[i][j].ss += new_elms; } for(int i = n; i >= 1; i--) rep2(j,1,n) { pii nxt = jump_down[i][j]; if(nxt.ff == i && nxt.ss == j) { jump_val_down[i][j] = {spc[i][j],0}; continue; } jump_val_down[i][j] = jump_val_down[nxt.ff][nxt.ss]; jump_val_down[i][j].ff += jump_val_down[i][j].ss; ll new_elms = get_sum(i,n,nxt.ss+1,j)+get_sum(i,nxt.ff-1,1,nxt.ss); jump_val_down[i][j].ff += new_elms; jump_val_down[i][j].ss += new_elms; } rep2(i,1,n) rep2(j,1,n) ans[i][j] = jump_val_up[i][j].ff + jump_val_down[i][j].ff-3+m; rep(i,m) cout << ans[points[i].ff][points[i].ss] << "\n"; }