#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define pb push_back #define pii pair<int, int> #define pll pair<ll, ll> #define st first #define nd second #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define debug true const int MAXN = 250 * 1000 + 17; const int MAXI = 2500; int spref[MAXI + 7][MAXI + 7]; pii a[MAXN]; int miny[MAXI + 7][MAXI + 7]; int minx[MAXI + 7][MAXI + 7]; int maxy[MAXI + 7][MAXI + 7]; int maxx[MAXI + 7][MAXI + 7]; ll dp1[MAXI + 7][MAXI + 7]; ll dp2[MAXI + 7][MAXI + 7]; ll ile (int a1, int b1, int a2, int b2) { return spref[a2][b2] - spref[a1 - 1][b2] - spref[a2][b1 - 1] + spref[a1 - 1][b1 - 1]; } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i < n; i ++) { cin >> a[i].st >> a[i].nd; } for (int i = 0; i < n; i ++) { spref[a[i].st][a[i].nd] ++; } for (int i = 0; i <= MAXI; i ++) { for (int j = 0; j <= MAXI; j ++) { minx[i][j] = MAXI + 3; miny[i][j] = MAXI + 3; } } for (int i = MAXI; i >= 1; i --) { for (int j = MAXI; j >= 1; j --) { if (spref[i][j] > 0) { maxx[i][j] = i; maxy[i][j] = j; } maxy[i][j] = max({maxy[i][j], maxy[i + 1][j], maxy[i][j + 1]}); maxx[i][j] = max({maxx[i][j], maxx[i + 1][j], maxx[i][j + 1]}); } } for (int i = 1; i <= MAXI; i ++) { for (int j = 1; j <= MAXI; j ++) { if (spref[i][j] > 0) { minx[i][j] = i; miny[i][j] = j; } minx[i][j] = min({minx[i][j], minx[i - 1][j], minx[i][j - 1]}); miny[i][j] = min({miny[i][j], miny[i - 1][j], miny[i][j - 1]}); spref[i][j] += spref[i - 1][j] + spref[i][j - 1] - spref[i - 1][j - 1]; } } for (int i = 1; i <= MAXI; i ++) { for (int j = MAXI; j >= 1; j --) { //cout << i << " " << j << ": " << ile(1, j, i, MAXI) << "\n"; //cout << minx[i - 1][j - 1] << " " << maxy[i + 1][j + 1] << "\n"; dp1[i][j] = ile(1, j, i, MAXI) + dp1[min(minx[i - 1][j - 1], i)][max(maxy[i + 1][j + 1], j)]; } } /*for (int i = 1; i <= MAXI; i ++) { for (int j = 1; j <= MAXI; j ++) { cout << i << " " << j << ": " << dp1[i][j] << "\n"; } } cout << "\n";*/ for (int i = MAXI; i >= 1; i --) { for (int j = 1; j <= MAXI; j ++) { dp2[i][j] = ile(i, 1, MAXI, j) + dp2[max(maxx[i + 1][j + 1], i)][min(miny[i - 1][j - 1], j)]; } } for (int i = 1; i <= MAXI; i ++) { for (int j = 1; j <= MAXI; j ++) { //cout << i << " " << j << ": " << dp2[i][j] << "\n"; } } for (int i = 0; i < n; i ++) { cout << dp1[a[i].st][a[i].nd] + dp2[a[i].st][a[i].nd] + ll(n - 3) << "\n"; } return 0; }