Hay Bale Perimeter

Farmer John has arranged N hay bales (1 ≤ N ≤ 50,000) on a 1,000,000 × 1,000,000 grid. Each bale occupies one unit square. The hay bales form a single connected region (neighbors are connected in the north, south, east or west directions), although this region might contain holes (empty regions completely surrounded by hay bales). Your task is to compute the external perimeter of the hay bale region. Note that boundaries adjacent to holes do not count towards the perimeter.

One way to view the problem is to first identify the exterior empty cells (those connected to infinity) via a flood fill, and then count the edges between hay bale cells and those exterior empty cells.

More formally, if we let S be the set of hay bale cells and E be the set of exterior empty cells discovered by flood filling the complement of S in a bounding box around the bale region, then the answer is given by:

[ Perimeter = \sum_{(x,y) \in S} \Bigl( [ (x+1,y) \in E ] + [ (x-1,y) \in E ] + [ (x,y+1) \in E ] + [ (x,y-1) \in E ] \Bigr), ]

where the bracket notation [condition] yields 1 if the condition is true, and 0 otherwise.

inputFormat

The first line contains an integer N, the number of hay bales. The next N lines each contain two integers x and y (0 ≤ x, y ≤ 1,000,000), indicating that a hay bale is located in cell (x, y). It is guaranteed that all hay bales form a single connected configuration.

outputFormat

Output a single integer representing the perimeter of the hay bale region (only counting borders that touch the exterior, not those adjacent to any holes).

sample

1
50 50

4