Making Okonomiyaki

Time limit1sMemory limit1024 MB

Summary

Two doughs and one meat piece sit on a pan of N cells; find the fewest flips that move a dough with stuck meat to the target cell, or report -1.

Level: Medium7 of 10
Topics: Simulation, Math, Greedy
Solved: No attempts yet

Problem

Right after a Japanese exam, Daegwak is making okonomiyaki with his friends.

The frying pan is a row of $N$ square cells. The leftmost cell is cell 1, and the rightmost cell is cell $N$ . Each okonomiyaki dough is a disk with two faces: a cooked side and a raw side. At the start, two doughs sit on different cells, each with the cooked side touching the pan and the raw side facing up. One cell with no dough holds a piece of meat.

Daegwak picks one dough, then picks one cell adjacent to the cell the dough occupies, and flips the dough onto that cell. For an integer $x (1 \leq x \leq N)$ , the cells adjacent to cell $x$ are cell 2 when $x = 1$ , cell $N - 1$ when $x = N$ , and cells $x-1$ and $x+1$ when $2 \leq x \leq N-1$ . A cell that already holds the other dough cannot be chosen. Each flip causes these changes:

The dough moves to the chosen cell.
The face touching the pan and the face facing up swap.
If the chosen cell has meat and the raw side touches the pan, the meat sticks to the dough. From then on, the meat moves with the dough whenever it is flipped.
If the chosen cell has meat and the cooked side touches the pan, the meat does not stick. It stays in its original cell and does not move when this dough is flipped later.

Daegwak's goal is for one of the two doughs to have the meat stuck to it, and for that dough to end up on a target cell. The dough without meat can be on any cell and can have either face up. Write a program that determines whether Daegwak can reach the goal and, if so, the minimum number of flips needed.

Input

The first line contains $N$ , the number of cells in the frying pan. $(3 \leq N \leq 1\,000\,000)$

The second line contains $p_1$ and $p_2$ , the starting cells of the two doughs, separated by a space. $(1 \leq p_1 < p_2 \leq N)$

The third line contains $M$ , the starting cell of the meat. $(1 \leq M \leq N;$ $M \ne p_1;$ $M \ne p_2)$

The fourth line contains $S$ , the cell where the dough with the meat must be after all flips are done. $(1 \leq S \leq N)$

Output

If Daegwak can reach the goal, print the minimum number of flips needed on one line. Otherwise, print -1 on one line.

Examples3

Example 1
Input
```
5
2 4
3
4
```
Expected output
```
2
```
Example 2
Input
```
5
1 2
4
4
```
Expected output
```
6
```
Example 3
Input
```
5
1 5
3
3
```
Expected output
```
-1
```