움얌얌

무한한 크기의 체스판에 $N$개의 룩(Rook)이 있다. 룩은 같은 행이나 같은 열에 있는 말을 공격할 수 있다. 초기 상태에서는 어떤 룩도 다른 룩을 공격할 수 없다. 즉, 모든 룩은 서로 다른 행에 있고, 서로 다른 열에 있다.

이 중 룩 하나를 구재현 코치 말로 대체한다. 구재현 코치는 상하좌우로 인접한 셀로 움직일 수 있다. 다만 룩에 공격당하는 셀, 즉 어떤 룩과 같은 행이나 같은 열에 있는 셀로는 움직일 수 없다.

구재현 코치는 맛있는 음식을 좋아한다. 코치가 있는 셀의 8방향(상하좌우와 대각선) 인접 셀에 룩이 있으면, 코치는 그 룩의 셀로 움직여 룩을 먹는다. 룩을 먹는 것은 룩에 공격당하는 것보다 우선한다.

구재현 코치는 가능한 한 많은 룩을 먹으려고 한다. 그 방법이 여러 가지라면 움직임이 가장 적은 방법을 택한다.

각 룩에 대해, 그 룩을 구재현 코치로 대체했다고 하자. 최대한 많은 룩을 먹기 위해 구재현 코치가 움직이는 횟수의 최솟값을 출력하라.

첫 번째 줄에 룩의 수 $N$ ($2 \le N \le 200\,000$)이 주어진다. 이후 $N$개의 줄에 각 룩의 좌표 $X_i, Y_i$ ($1 \le X_i, Y_i \le 10^6$)가 주어진다.

모든 룩은 서로 다른 행과 서로 다른 열에 있다. 즉, $i \neq j$이면 $X_i \neq X_j$이고 $Y_i \neq Y_j$이다.

$N$개의 줄에 걸쳐 정수를 하나씩 출력하라. $i$번째 줄에는 $i$번째 룩을 구재현 코치로 대체했을 때, 최대한 많은 룩을 먹기 위해 구재현 코치가 움직이는 횟수의 최솟값을 출력한다.