문제

은영이는 건강을 위해 유성구 도심에서 열리는 마라톤 대회에 참가하기로 했다. 마라톤 코스는 순서대로 방문해야 하는 $N$개의 체크포인트로 구성되어 있으며, $1$번 체크포인트는 출발점, $N$번 체크포인트는 결승점이다.

은영이는 마라톤 코스의 모든 체크포인트를 순서대로 방문해야 하지만, 조금이라도 더 빨리 도착하기 위해 최대 하나의 체크포인트를 건너뛰어 총 이동 거리를 줄이려고 한다. 단, $1$번과 $N$번 체크포인트는 대회 운영상 너무 눈에 띄기 때문에 건너뛸 수 없다.

은영이가 최대 하나의 체크포인트를 건너뛰었을 때 이동해야 하는 최소 거리를 구한다.

도심의 격자 도로망을 따라 이동하므로, 두 체크포인트 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 $|x_1 - x_2| + |y_1 - y_2|$로 계산한다. 이러한 거리 측정 방식은 도심의 도로가 $x$축 또는 $y$축에 평행하여 대각선으로 가로질러 갈 수 없는 상황을 반영하며, 흔히 "맨해튼 거리"라고 불린다.

입력

첫째 줄에 체크포인트의 개수 $N$이 주어진다. ($3 \le N \le 100\,000$)

다음 $N$개의 줄에는 각 체크포인트의 좌표 $x$와 $y$가 공백으로 구분되어 주어진다. ($-1\,000 \le x \le 1\,000$; $-1\,000 \le y \le 1\,000$) 체크포인트는 방문해야 하는 순서대로 제공된다.

마라톤 코스는 여러 번 겹칠 수 있으며, 서로 다른 순서의 체크포인트가 동일한 좌표에 위치할 수도 있다. 만약 은영이가 그런 체크포인트를 건너뛴다면, 해당 순서의 체크포인트 하나만 건너뛰는 것이며 동일한 위치의 다른 체크포인트들까지 건너뛰는 것은 아니다.

출력

은영이가 최대 하나의 체크포인트를 건너뛰었을 때 가능한 최소 이동 거리를 출력한다.

예제 입력 1

4
0 0
8 3
11 -1
10 0

예제 출력 1

14