Problem J
Tiny House Race

Tiny House Chess is a variant of chess played on a $4 \times 4$ board using some standard and some new pieces. Two pieces of interest are the King, from standard chess, and the Wazir, which is a new piece.

The King is able to move one space in any direction (i.e. up, down, left, right, or any of the diagonals). The Wazir is able to move one space orthogonally (i.e. up, down, left, or right).
In Tiny House Chess you can use a turn to either move one of your pieces or place another piece on the board in an empty square.

Figure 1: Movement patterns of the King and Wazir respectively

Your friend John has become enamoured with the game and plays it for hours online. But unfortunately most games are pretty short, leaving a lot of downtime between games. John likes to use this time to do puzzles for practice.

For each puzzle he uses a $n \times n$ board and selects three distinct squares: the king square, the spawn square, and the target square. Initially, the board contains only a King on the king square.

The goal is to occupy the target square (with either a King or a Wazir) in as few turns as possible. Each turn, John chooses exactly one action:

• move one piece currently on the board (King or any Wazir), or

• if the spawn square is empty, place a new Wazir on the spawn square.

John would like you to write a program that computes the minimum number of turns required if he were to play optimally.

Input

The input consists of four lines:

• The first line contains a single integer $n$ ($2 \leq n \leq 10^9$), the size of the board.

• The second line contains two integers $k_r$ and $k_c$ ($1 \leq k_r, k_c \leq n$), the row and column of the “king” square.

• The third line contains two integers $s_r$ and $s_c$ ($1 \leq s_r, s_c \leq n$), the row and column of the “spawn” square.

• The fourth line contains two integers $t_r$ and $t_c$ ($1 \leq t_r, t_c \leq n$), the row and column of the “target” square.

Output

Print a single line containing the number of turns it will take John to occupy the target square if he plays optimally.

3
1 1
3 3
2 1

1

5
1 1
1 4
5 3

4