선장

바이트아사르 선장은 둘도 없는 일등항해사 바이텍과 함께 바이트 해를 항해한다. 바이트 해에는 섬이 $n$개 있고, 섬에는 1부터 $n$까지 번호가 붙어 있다. 선장의 배는 지금 1번 섬에 정박해 있고, 선장은 $n$번 섬까지 항해할 계획이다.

항해 중에 배는 항상 동서남북 네 방향 중 하나로만 움직인다. 매 순간 선장과 일등항해사 중 한 사람이 키를 잡는다. 배가 90도 방향을 바꿀 때마다 두 사람은 키를 교대한다.

배는 가는 길에 다른 섬에 들를 수 있다. 섬에 들를 때마다 선장은 다음 구간에서 자기가 먼저 키를 잡을지 말지를 정할 수 있다. 다시 말해 한 섬에서 다른 섬으로 가는 구간마다, 한 사람은 배가 남북으로 움직이는 동안 키를 잡고 다른 사람은 배가 동서로 움직이는 동안 키를 잡는다. 특히 어떤 구간이 네 방향 중 한 방향으로만 곧게 이어진다면, 그 구간에서는 한 사람만 키를 잡는다.

선장은 앞으로의 항로와 두 사람의 역할 분담을 정해서 자기가 키를 잡는 시간을 최대한 줄이려고 한다. 항로가 얼마나 길어지는지는 신경 쓰지 않는다. 배는 한 시간에 한 단위 거리를 가는 일정한 속력으로 움직인다.

첫째 줄에 섬의 수 $n$ ($2 \le n \le 200\,000$)이 주어진다. 바이트 해 위에는 동서남북 방향과 평행한 축을 가진 좌표계가 놓여 있고, 각 섬은 한 점으로 나타낸다. 다음 $n$개의 줄에 섬의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번 섬의 좌표 $x_i$, $y_i$ ($0 \le x_i, y_i \le 1\,000\,000\,000$)가 정수로 주어진다. 좌표가 같은 두 섬은 없다.

1번 섬에서 $n$번 섬까지 가는 동안 선장이 키를 잡아야 하는 최소 시간을 정수로 한 줄에 출력한다.

첫 번째 예제에서 선장은 그림과 같은 항로를 택할 수 있다. 1번 섬 (좌표 $(2, 2)$)에서 4번 섬 (좌표 $(7, 1)$)으로 가는 동안 선장은 배가 남쪽으로 움직이는 한 시간만 키를 잡는다. 두 번째 구간에서는 배가 동쪽으로 움직이는 동안만 키를 잡는다.