Problem Description

Translated from CEOI 2024 Day1 T3 "Text editor"

Robert is participating in the 2024 CEOI programming competition. He has almost completed the code for the hardest problem of the day, and he is confident he can score full marks! However, there is a small detail issue: he made a typo! Even worse, his beloved mouse, which he has been using since 2008, has completely stopped working, unresponsive. Therefore, he can only move the cursor to find the typo using the arrow keys on the keyboard.

Robert's program has $N$ lines, with each line having lengths $l_1, l_2, \ldots, l_N$. Robert always ends his program with an empty line, so $l_N = 0$. The cursor can be placed between two characters, or at the beginning or end of a line. Thus, the $i$-th line has $l_i + 1$ available cursor positions (referred to as columns), numbered from $1$ to $l_i + 1$. For example, here is the situation where the cursor is at the 6th column of the 2nd line:

Robert wants to move the cursor from the $s_l$-th line and $s_c$-th column to the $e_l$-th line and $e_c$-th column. He wants to find out the minimum number of key presses required.

The use of horizontal arrow keys is straightforward. Pressing the left key moves the cursor to the previous column, or to the end of the previous line if the cursor is at the beginning of a line. Similarly, pressing the right key moves the cursor to the next column, or to the beginning of the next line if the cursor is at the end of a line.

For example, the movement by the left key can look like this:

And the movement by the right key can look like this:

Pressing the left key at the very beginning of the file or the right key at the very end of the file will have no effect.

The use of vertical arrow keys is slightly more complex. Pressing the up key moves the cursor to the previous line, and pressing the down key moves the cursor to the next line, with the column number remaining unchanged. However, if this would place the cursor beyond the end of the new line, the cursor jumps to the end of that line.

For example, the movement by the up key can look like this:

And the movement by the down key can look like this:

If pressing the up key or down key would move the cursor to a non-existent line, the cursor will not move at all.

Input Format

The first line of input contains an integer $N$, the number of lines in Robert's program.

The second line contains two space-separated integers $s_l$ and $s_c$, the initial cursor position.

Similarly, the third line contains two space-separated integers $e_l$ and $e_c$, the target cursor position.

The fourth line contains $N$ space-separated integers $l_1, l_2, \ldots, l_N$, the lengths of each line.

Output Format

Output a single line containing an integer, the minimum number of key presses required to move the cursor from $(s_l, s_c)$ to $(e_l, e_c)$.

Sample Input and Output

Sample Input #1

5
3 1
2 8
7 10 9 9 0

Sample Output #1

3

Sample Input #2

5
1 20
3 25
25 10 40 35 0

Sample Output #2

16

Notes/Hints

Sample Explanation 1

Robert can move the cursor to the target position by pressing the up key, left key, and down key in sequence:

Alternatively, he can also move the cursor to the target position just as quickly by pressing the left key, up key, and down key.

Sample Explanation 2

It is easy to prove that it is not possible to reach the target position using at most two key presses.

The shortest possible key sequence is pressing the down key twice followed by fourteen presses of the right key.

For all input data, the following conditions are satisfied:

• $1 \leq N \leq 10^6$
• $0 \leq l_i \leq 10^9\ (1 \leq i \leq n)$
• $l_N = 0$
• $1 \leq s_l, e_l \leq N$
• $1 \leq s_c \leq l_{s_l} + 1$
• $1 \leq e_c \leq l_{e_l} + 1$

Detailed subtask additional restrictions and scores are as follows:

见题面 Input 部分

见题面 Output 部分