P10803 [CEOI 2024] Text Editor

**This problem is translated from [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day 1 T3「[Text editor](https://ceoi2024.fi.muni.cz/page/tasks/statements/editor.pdf)」.** Robert is participating in the CEOI 2024 programming contest. He has almost finished the code for the hardest problem of the day, and he is sure he will get a full score. But there is a tiny detail: he mistyped one character. Even worse, his beloved mouse, which he has used since 2008, has completely stopped working and does not respond at all. Therefore, he can only use the arrow keys on the keyboard to move the cursor to find that typo. Robert's program has $N$ lines, with lengths $l_1, l_2, \ldots, l_N$. Robert always ends the program with an empty line, so $l_N = 0$. The cursor can be placed between two characters, and also at the beginning or end of a line. Therefore, line $i$ has $l_i + 1$ available cursor positions (called columns), numbered from $1$ to $l_i + 1$. For example, the following shows the cursor at line $2$, column $6$:  Robert wants to move the cursor from column $s_c$ in line $s_l$ to column $e_c$ in line $e_l$. He wants to find the minimum number of key presses needed. Using the horizontal arrow keys is simple. Pressing **Left** moves the cursor to the previous column, unless the cursor is at the beginning of a line, in which case it moves to the end of the previous line. Similarly, pressing **Right** moves the cursor to the next column, or if the cursor is at the end of a line, it moves to the beginning of the next line. For example, **Left** can move like this:  And **Right** can move like this:  Pressing **Left** at the very beginning of the file, or pressing **Right** at the very end of the file, has no effect. Using the vertical arrow keys is a bit more complicated. Pressing **Up** moves the cursor to the previous line, and pressing **Down** moves it to the next line, keeping the same column number. 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, **Up** can move like this:  And **Down** can move like this:  If pressing **Up** or **Down** would move the cursor to a line that does not exist, then the cursor does not move at all.

The first line contains an integer $N$, the number of lines in Robert's program. The second line contains two integers $s_l$ and $s_c$ separated by spaces, describing the initial cursor position. Similarly, the third line contains two integers $e_l$ and $e_c$ separated by spaces, describing the target cursor position. The fourth line contains $N$ integers $l_1, l_2, \ldots, l_N$ separated by spaces, where $l_i$ is the length of line $i$.

Output one 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 Explanation 1** Robert can move the cursor to the target position by pressing, in order, **Up**, **Left**, and **Down**:  Alternatively, he can press **Left**, **Up**, and **Down** to reach the target position just as fast. **Sample Explanation 2** It is easy to prove that it is impossible to reach the target position using at most two key presses. The shortest possible key sequence is pressing **Down** twice and then pressing **Right** fourteen times. For all input data, the following constraints hold: - $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$. The detailed additional constraints and scores for the subtasks are given in the table below. | Subtask | Additional Constraints | Score | | :--: | :--: | :--: | | $1$ | $N \leq 2$ | $5$ | | $2$ | $N \leq 1\,000, l_i \leq 5\,000\ (1 \leq i \leq N)$ | $14$ | | $3$ | $N \leq 1\,000$ | $26$ | | $4$ | $l_i = l_j\ (1 \leq i, j \leq N - 1)$ | $11$ | | $5$ | No additional constraints. | $44$ | Translated by ChatGPT 5