Text Editor

Robert is competing in CEOI 2024. He has almost finished his solution to the hardest problem of the day and is pretty sure it will score 100 points. There is one small problem: he made a typo. His favorite mouse, which he has used since 2008, has finally broken and does not respond at all. He has to move the cursor to the typo with the arrow keys on his keyboard.

Robert's program has $N$ lines with lengths $l_1, l_2, \ldots, l_N$. Robert always ends his programs with an empty line, so $l_N = 0$. The cursor can be placed between two characters, or at the start or end of a line. Line $i$ therefore has $l_i + 1$ possible cursor positions (called columns), numbered from 1 to $l_i + 1$. For example, a cursor on line 2 in column 6 sits after the fifth character of that line.

Robert wants to move the cursor from line $s_l$, column $s_c$ to line $e_l$, column $e_c$. Find the minimum number of key presses needed to do so.

The horizontal arrow keys are simple. Pressing left moves the cursor to the previous column, or to the end of the previous line if the cursor is at the start of a line. Pressing right moves the cursor to the next column, or to the start of the next line if the cursor is at the end of a line. Pressing left at the very start of the file or right at the very end of the file has no effect.

The vertical arrow keys are slightly more complicated. Pressing up moves the cursor to the previous line, and pressing down moves it to the next line, without changing the column number. If that column is past the end of the new line, the cursor moves to the end of that line instead. If up or down would move the cursor to a line that does not exist, the cursor does not move.

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

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

The third line contains two 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 length of each line.

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

$1 \leq N \leq 10^6$

$0 \leq l_i \leq 10^9$ for each $i$ such that $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$