Ideal City Pairwise Distance Sum

In an ideal city, there are \(N\) blocks placed on an infinite square grid. The cell at the \(x\)-th row and \(y\)-th column is denoted by \((x,y)\) with \((0,0)\) being the upper‐left cell. A block can only be placed in a cell \((x,y)\) if \(1 \le x,y \le 2^{31}-2\). Each block covers exactly one cell and its coordinate is used to denote its position on the grid. Two blocks are considered adjacent if their corresponding cells share a side. An ideal city satisfies the following conditions:

• For any two blank cells (cells without a block), there exists a sequence of adjacent blank cells connecting them.
• For any two non‐blank cells (cells with a block), there exists a sequence of adjacent non‐blank cells connecting them.

When traversing the city, a jump is defined as moving from one block to an adjacent block (you cannot step into a blank cell). Suppose the coordinates of the \(N\) blocks are \(v_0,v_1,\dots,v_{N-1}\). For any two distinct blocks \(v_i\) and \(v_j\), let \(d(v_i,v_j)\) be the minimum number of jumps needed to go from \(v_i\) to \(v_j)\). For example, consider the following 11-block ideal city (the blocks' coordinates are given):

\(v_0=(2,5)\), \(v_1=(2,6)\), \(v_2=(3,3)\), \(v_3=(3,6)\), \(v_4=(4,3)\), \(v_5=(4,4)\), \(v_6=(4,5)\), \(v_7=(4,6)\), \(v_8=(5,3)\), \(v_9=(5,4)\), \(v_{10}=(5,6)\).

Some example distances are \(d(v_1,v_3)=1\), \(d(v_1,v_8)=6\), \(d(v_6,v_{10})=2\), and \(d(v_9,v_{10})=4\).

Your task is to compute the sum

[ S=\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1} d(v_i,v_j), ]

given an ideal city configuration. It is guaranteed that the blocks form a connected configuration (and the corresponding blank cells also form a connected region).

inputFormat

The first line contains an integer \(N\) representing the number of blocks. Each of the next \(N\) lines contains two integers \(x\) and \(y\), the coordinates of a block. It is guaranteed that the blocks form an ideal city, i.e.:

• The blocks (non-blank cells) are connected.
• The blank cells are also connected.

outputFormat

Output a single integer \(S\), the sum of the minimum jumps between every pair of blocks.

sample

2
2 5
2 6

1