Farmer John colocou $N$ fardos de feno, $(1 \le N \le 50,000)$, no meio de um de seus campos. Se considerarmos o campo uma grade de $1,000,000$ $x$ $1,000,000$ células quadradas de $1$ $x$ $1$, cada fardo ocupa exatamente uma célula (naturalmente, dois fardos não ocupam a mesma célula).

FJ percebe que todos os seus fardos formam uma única região conexa grande: partindo de qualquer fardo, é possível alcançar qualquer outro dando uma sequência de passos para fardos diretamente adjacentes ao norte, sul, leste ou oeste. A região pode, porém, conter “buracos”, isto é, regiões vazias completamente cercadas por fardos.

Ajude FJ a determinar o perímetro da região formada por seus fardos. Os buracos não contribuem para o perímetro.

Entrada

• Linha 1: o número de fardos de feno, $N$.

• As próximas $N$ linhas, isto é, as linhas $2\ldots1+N$: cada linha contém a posição ($x$, $y$) de um fardo; $x$ e $y$ são inteiros no intervalo $1\ldots1,000,000$. A posição $(1,1)$ é a célula inferior esquerda do campo, e $(1000000,1000000)$ é a superior direita.

Saída

• Linha 1: o perímetro da região conexa de fardos.

Exemplos

Entrada 1

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

Saída 1

14

Explicação

A região conexa formada pelos fardos tem este aspecto:

XX 
X XX
XXX

O perímetro da região conexa é $14$ (por exemplo, o lado esquerdo contribui com comprimento $3$ para o total). O buraco no meio não contribui para esse número.

Autor do problema: Brian Dean, 2013