Problem:
 Score : 2200 points    Problem Statement You are given positions (X_i, Y_i) of N enemy rooks on an infinite chessboard.
No two rooks attack each other (at most one rook per row or column).  You're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.  You can't enter a cell that is being attacked by a rook.
Additionally, you can't move diagonally to an empty cell (but you can beat a rook diagonally).  (So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)  For each rook, consider replacing it with a king, and find the minimum possible number of moves
    needed to beat the maximum possible number of rooks.      Constraints  2 \leq N \leq 200\,000  1 \leq X_i, Y_i \leq 10^6  X_i \neq X_j  Y_i \neq Y_j  All values in input are integers.         Input Input is given from Standard Input in the following format.  N  X_1  Y_1  X_2  Y_2  \vdots  X_N  Y_N       Output Print N lines.
The i -th line is for scenario of replacing the rook at (X_i, Y_i) with your king.
This line should contain one integer: the minimum number of moves to beat M_i rooks
    where M_i denotes the maximum possible number of beaten rooks in this scenario (in infinite time).        Sample Input 1 6
1 8
6 10
2 7
4 4
9 3
5 1      Sample Output 1 5
0
7
5
0
0  See the drawing below.
If we replace rook 3 with a king, we can beat at most two other rooks.
The red path is one of optimal sequences of moves: beat rook 1,
    then keep going down and right until you can beat rook 4.
There are 7 steps and that's the third number in the output.   x-coordinate increases from left to right,
    while y increases bottom to top.  Starting from rook 2, 5 or 6, we can't beat any other rook.
The optimal number of moves is 0.       Sample Input 2 5
5 5
100 100
70 20
81 70
800 1      Sample Output 2 985
985
1065
1034
0       Sample Input 3 10
2 5
4 4
13 12
12 13
14 17
17 19
22 22
16 18
19 27
25 26      Sample Output 3 2
2
9
9
3
3
24
5
0
25

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    xxx = inp[1::2]
    yyy = inp[2::2]
    xxx_idx = np.argsort(xxx)
    yyy_idx = np.argsort(yyy)
    
    
    xxx_num = np.argsort(xxx_idx)
    yyy_num = np.argsort(yyy_idx)

    
    

    
    
    
    

    def get_xy_by_xi(xi):
        i = xxx_idx[xi]
        return xxx[i], yyy[i]

    def calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, rnxi, rook_cnt):
        lpx, lpy = get_xy_by_xi(lpxi)
        rnx, rny = get_xy_by_xi(rnxi)

        diag_t = abs(rnx - lpx) + abs(rny - lpy) - rook_cnt

        lllt = llt + abs(rnx - lx) + abs(rny - ly) + diag_t
        llrt = llt + abs(lx - lpx) + abs(ly - lpy) + diag_t
        lrlt = lrt + abs(rnx - rx) + abs(rny - ry) + diag_t
        lrrt = lrt + abs(rx - lpx) + abs(ry - lpy) + diag_t
        rllt = rlt + abs(rnx - lx) + abs(rny - ly) + diag_t
        rlrt = rlt + abs(lx - lpx) + abs(ly - lpy) + diag_t
        rrlt = rrt + abs(rnx - rx) + abs(rny - ry) + diag_t
        rrrt = rrt + abs(rx - lpx) + abs(ry - lpy) + diag_t

        llt = min(lllt, lrlt)
        lrt = min(llrt, lrrt)
        rlt = min(rllt, rrlt)
        rrt = min(rlrt, rrrt)
        
        
        

        return lpx, lpy, rnx, rny, llt, lrt, rlt, rrt

    
    free = np.zeros(n, dtype=np.int8)

    for i in range(n):
        xi = xxx_num[i]
        yi = yyy_num[i]
        px_i = -1 if xi == 0 else xxx_idx[xi - 1]
        nx_i = -2 if xi == n - 1 else xxx_idx[xi + 1]
        py_i = -3 if yi == 0 else yyy_idx[yi - 1]
        ny_i = -4 if yi == n - 1 else yyy_idx[yi + 1]
        if px_i == py_i or px_i == ny_i:
            free[xi - 1] = 1
        if nx_i == py_i or nx_i == ny_i:
            free[xi] = 1

    
    
    
    free_l = np.zeros(n, dtype=np.int64)
    free_r = np.zeros(n, dtype=np.int64)
    l = 0
    for xi in range(n - 1):
        if free[xi] == 0:
            l = xi + 1
        free_l[xi + 1] = l
    r = n - 1
    free_r[r] = r
    for xi in range(n - 2, -1, -1):
        if free[xi] == 0:
            r = xi
        free_r[xi] = r

    
    
    

    
    
    
    
    extra_l = np.zeros(n, dtype=np.int64)
    extra_r = np.zeros(n, dtype=np.int64)
    INF = 10 ** 18
    lxi = 0
    while lxi < n:
        rxi = free_r[lxi]

        if lxi == rxi:
            lxi = rxi + 1
            continue

        li = xxx_idx[lxi]
        ri = xxx_idx[rxi]
        lyi = yyy_num[li]
        ryi = yyy_num[ri]
        lyi, ryi = min(lyi, ryi), max(lyi, ryi)

        original_li = lxi
        lx = xxx[li]
        ly = yyy[li]
        rx = xxx[ri]
        ry = yyy[ri]
        llt, lrt, rlt, rrt = 0, INF, INF, 0

        

        while True:
            px_i = -1 if lxi == 0 else xxx_idx[lxi - 1]
            py_i = -2 if lyi == 0 else yyy_idx[lyi - 1]
            nx_i = -3 if rxi == n - 1 else xxx_idx[rxi + 1]
            ny_i = -4 if ryi == n - 1 else yyy_idx[ryi + 1]
            
            if px_i == py_i:
                lpxi = free_l[lxi - 1]
                rook_cnt = lxi - lpxi

                if nx_i == ny_i:
                    rnxi = free_r[rxi + 1]
                    rook_cnt += rnxi - rxi
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, rnxi, rook_cnt)
                    lxi = lpxi
                    rxi = rnxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    vyi = yyy_num[xxx_idx[rxi]]
                    lyi, ryi = min(lyi, ryi, uyi, vyi), max(lyi, ryi, uyi, vyi)
                    
                else:
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, lpxi, rook_cnt)
                    lxi = lpxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    lyi, ryi = min(lyi, ryi, uyi), max(lyi, ryi, uyi)
                    

            elif px_i == ny_i:
                lpxi = free_l[lxi - 1]
                rook_cnt = lxi - lpxi

                if nx_i == py_i:
                    rnxi = free_r[rxi + 1]
                    rook_cnt += rnxi - rxi
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, rnxi, rook_cnt)
                    lxi = lpxi
                    rxi = rnxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    vyi = yyy_num[xxx_idx[rxi]]
                    lyi, ryi = min(lyi, ryi, uyi, vyi), max(lyi, ryi, uyi, vyi)
                    
                else:
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, lpxi, rook_cnt)
                    lxi = lpxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    lyi, ryi = min(lyi, ryi, uyi), max(lyi, ryi, uyi)
                    

            elif nx_i == ny_i or nx_i == py_i:
                rnxi = free_r[rxi + 1]
                rook_cnt = rnxi - rxi
                
                lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                    calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, rnxi, rnxi, rook_cnt)
                rxi = rnxi
                vyi = yyy_num[xxx_idx[rxi]]
                lyi, ryi = min(lyi, ryi, vyi), max(lyi, ryi, vyi)
                

            else:
                extra_l[original_li] = min(llt, lrt)
                extra_r[original_li] = min(rlt, rrt)
                break

        lxi = rxi + 1

    
    

    ans = np.zeros(n, dtype=np.int64)
    for i in range(n):
        xi = xxx_num[i]
        x = xxx[i]
        y = yyy[i]
        lxi = free_l[xi]
        lx = xxx[xxx_idx[lxi]]
        ly = yyy[xxx_idx[lxi]]
        rxi = free_r[xi]
        rx = xxx[xxx_idx[rxi]]
        ry = yyy[xxx_idx[rxi]]
        lt = extra_l[lxi]
        rt = extra_r[lxi]
        diag = abs(rx - lx) + abs(ry - ly) - (rxi - lxi)
        rlt = abs(rx - x) + abs(ry - y) + diag
        lrt = abs(x - lx) + abs(y - ly) + diag
        ans[i] = min(lt + rlt, rt + lrt)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Solution (Python):
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    xxx = inp[1::2]
    yyy = inp[2::2]
    xxx_idx = np.argsort(xxx)
    yyy_idx = np.argsort(yyy)
    
    
    xxx_num = np.argsort(xxx_idx)
    yyy_num = np.argsort(yyy_idx)

    
    

    
    
    
    

    def get_xy_by_xi(xi):
        i = xxx_idx[xi]
        return xxx[i], yyy[i]

    def calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, rnxi, rook_cnt):
        lpx, lpy = get_xy_by_xi(lpxi)
        rnx, rny = get_xy_by_xi(rnxi)

        diag_t = abs(rnx - lpx) + abs(rny - lpy) - rook_cnt

        lllt = llt + abs(rnx - lx) + abs(rny - ly) + diag_t
        llrt = llt + abs(lx - lpx) + abs(ly - lpy) + diag_t
        lrlt = lrt + abs(rnx - rx) + abs(rny - ry) + diag_t
        lrrt = lrt + abs(rx - lpx) + abs(ry - lpy) + diag_t
        rllt = rlt + abs(rnx - lx) + abs(rny - ly) + diag_t
        rlrt = rlt + abs(lx - lpx) + abs(ly - lpy) + diag_t
        rrlt = rrt + abs(rnx - rx) + abs(rny - ry) + diag_t
        rrrt = rrt + abs(rx - lpx) + abs(ry - lpy) + diag_t

        llt = min(lllt, lrlt)
        lrt = min(llrt, lrrt)
        rlt = min(rllt, rrlt)
        rrt = min(rlrt, rrrt)
        
        
        

        return lpx, lpy, rnx, rny, llt, lrt, rlt, rrt

    
    free = np.zeros(n, dtype=np.int8)

    for i in range(n):
        xi = xxx_num[i]
        yi = yyy_num[i]
        px_i = -1 if xi == 0 else xxx_idx[xi - 1]
        nx_i = -2 if xi == n - 1 else xxx_idx[xi + 1]
        py_i = -3 if yi == 0 else yyy_idx[yi - 1]
        ny_i = -4 if yi == n - 1 else yyy_idx[yi + 1]
        if px_i == py_i or px_i == ny_i:
            free[xi - 1] = 1
        if nx_i == py_i or nx_i == ny_i:
            free[xi] = 1

    
    
    
    free_l = np.zeros(n, dtype=np.int64)
    free_r = np.zeros(n, dtype=np.int64)
    l = 0
    for xi in range(n - 1):
        if free[xi] == 0:
            l = xi + 1
        free_l[xi + 1] = l
    r = n - 1
    free_r[r] = r
    for xi in range(n - 2, -1, -1):
        if free[xi] == 0:
            r = xi
        free_r[xi] = r

    
    
    

    
    
    
    
    extra_l = np.zeros(n, dtype=np.int64)
    extra_r = np.zeros(n, dtype=np.int64)
    INF = 10 ** 18
    lxi = 0
    while lxi < n:
        rxi = free_r[lxi]

        if lxi == rxi:
            lxi = rxi + 1
            continue

        li = xxx_idx[lxi]
        ri = xxx_idx[rxi]
        lyi = yyy_num[li]
        ryi = yyy_num[ri]
        lyi, ryi = min(lyi, ryi), max(lyi, ryi)

        original_li = lxi
        lx = xxx[li]
        ly = yyy[li]
        rx = xxx[ri]
        ry = yyy[ri]
        llt, lrt, rlt, rrt = 0, INF, INF, 0

        

        while True:
            px_i = -1 if lxi == 0 else xxx_idx[lxi - 1]
            py_i = -2 if lyi == 0 else yyy_idx[lyi - 1]
            nx_i = -3 if rxi == n - 1 else xxx_idx[rxi + 1]
            ny_i = -4 if ryi == n - 1 else yyy_idx[ryi + 1]
            
            if px_i == py_i:
                lpxi = free_l[lxi - 1]
                rook_cnt = lxi - lpxi

                if nx_i == ny_i:
                    rnxi = free_r[rxi + 1]
                    rook_cnt += rnxi - rxi
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, rnxi, rook_cnt)
                    lxi = lpxi
                    rxi = rnxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    vyi = yyy_num[xxx_idx[rxi]]
                    lyi, ryi = min(lyi, ryi, uyi, vyi), max(lyi, ryi, uyi, vyi)
                    
                else:
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, lpxi, rook_cnt)
                    lxi = lpxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    lyi, ryi = min(lyi, ryi, uyi), max(lyi, ryi, uyi)
                    

            elif px_i == ny_i:
                lpxi = free_l[lxi - 1]
                rook_cnt = lxi - lpxi

                if nx_i == py_i:
                    rnxi = free_r[rxi + 1]
                    rook_cnt += rnxi - rxi
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, rnxi, rook_cnt)
                    lxi = lpxi
                    rxi = rnxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    vyi = yyy_num[xxx_idx[rxi]]
                    lyi, ryi = min(lyi, ryi, uyi, vyi), max(lyi, ryi, uyi, vyi)
                    
                else:
                    
                    lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                        calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, lpxi, lpxi, rook_cnt)
                    lxi = lpxi
                    uyi = yyy_num[xxx_idx[lxi]]
                    lyi, ryi = min(lyi, ryi, uyi), max(lyi, ryi, uyi)
                    

            elif nx_i == ny_i or nx_i == py_i:
                rnxi = free_r[rxi + 1]
                rook_cnt = rnxi - rxi
                
                lx, ly, rx, ry, llt, lrt, rlt, rrt = \
                    calc_time(lx, ly, rx, ry, llt, lrt, rlt, rrt, rnxi, rnxi, rook_cnt)
                rxi = rnxi
                vyi = yyy_num[xxx_idx[rxi]]
                lyi, ryi = min(lyi, ryi, vyi), max(lyi, ryi, vyi)
                

            else:
                extra_l[original_li] = min(llt, lrt)
                extra_r[original_li] = min(rlt, rrt)
                break

        lxi = rxi + 1

    
    

    ans = np.zeros(n, dtype=np.int64)
    for i in range(n):
        xi = xxx_num[i]
        x = xxx[i]
        y = yyy[i]
        lxi = free_l[xi]
        lx = xxx[xxx_idx[lxi]]
        ly = yyy[xxx_idx[lxi]]
        rxi = free_r[xi]
        rx = xxx[xxx_idx[rxi]]
        ry = yyy[xxx_idx[rxi]]
        lt = extra_l[lxi]
        rt = extra_r[lxi]
        diag = abs(rx - lx) + abs(ry - ly) - (rxi - lxi)
        rlt = abs(rx - x) + abs(ry - y) + diag
        lrt = abs(x - lx) + abs(y - ly) + diag
        ans[i] = min(lt + rlt, rt + lrt)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))