Marathon 1

Farmer John decided that the cows on his farm are out of shape, so he organized a marathon for them. Seungwon, his favorite cow, is entering the race.

The course has $N$ checkpoints. The marathon ends once a cow starts at checkpoint 1, visits every checkpoint in order of its number, and finishes at checkpoint $N$. Seungwon is lazy, and now that the race is about to start he cannot be bothered, so he plans to secretly skip one of the checkpoints in the middle. Skipping checkpoint 1 or checkpoint $N$ would be too obvious, so he will not skip either of those two.

If Seungwon may skip one checkpoint while he runs, what is the shortest distance he has to run?

The cow marathon takes place in the middle of downtown Seoul, so distance is measured as taxicab distance (Manhattan distance). The distance between $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$, where $|x|$ denotes absolute value.

The first line contains the number of checkpoints $N$. ($3 \le N \le 100000$)

Each of the next $N$ lines contains two integers. The first integer on line $i$ is the $x$ coordinate of checkpoint $i$, and the second is its $y$ coordinate. ($-1000 \le x, y \le 1000$)

Two different checkpoints may share the same coordinates. When Seungwon skips a checkpoint he skips only that one number, and he still visits every other checkpoint that sits on the same point.

Print the shortest distance Seungwon has to run when he skips exactly one checkpoint.

In the first sample Seungwon may skip checkpoint 2 or checkpoint 3. Skipping checkpoint 2 gives the route $(0, 0) \to (11, -1) \to (10, 0)$, whose length is 14. He cannot run any shorter than that.