Text Editor Cursor Navigation

Robert is participating in the 2024 CEOI programming contest. He has nearly finished the hardest problem of the day but made a tiny typo. To correct it, he must move the cursor through his code using only the keyboard’s arrow keys because his beloved mouse has stopped working.

The program consists of \(N\) lines with respective lengths \(l_1, l_2, \ldots, l_N\), where the last line is always empty (i.e. \(l_N = 0\)). In the \(i\)-th line, there are \(l_i+1\) valid cursor positions (columns), numbered from 1 to \(l_i+1\). The cursor may be positioned between any two characters as well as at the beginning or the end of a line.

The arrow keys function as follows:

• Left key: Moves the cursor one position to the left. If the cursor is at the beginning of a line (column 1), it will move to the end of the previous line (column \(l_{i-1}+1\)), provided that a previous line exists. If the cursor is already at the very start of the file, the key does nothing.
• Right key: Moves the cursor one position to the right. If the cursor is at the end of a line (column \(l_i+1\)), it will move to the beginning of the next line (column 1), provided that there is a next line. If the cursor is at the very end of the file, the key does nothing.
• Up key: Moves the cursor to the line above, keeping the same column number if possible. If the target line does not have that many columns (i.e. if \(c > l_{i-1}+1\)), the cursor jumps to the end of that line (column \(l_{i-1}+1\)). If there is no previous line, nothing happens.
• Down key: Moves the cursor to the line below, keeping the same column number if possible. If that line is shorter (i.e. if \(c > l_{i+1}+1\)), the cursor moves to its end (column \(l_{i+1}+1\)). If there is no next line, the key does nothing.

Given the starting position \((s_l, s_c)\) and the target position \((e_l, e_c)\), compute the minimum number of key presses required to move the cursor from the start to the target position.

inputFormat

The first line contains five integers: \(N\), \(s_l\), \(s_c\), \(e_l\), and \(e_c\) where:

• \(N\) is the number of lines in the program.
• \(s_l\) and \(s_c\) represent the starting line and column.
• \(e_l\) and \(e_c\) represent the target line and column.

The second line contains \(N\) integers: \(l_1, l_2, \ldots, l_N\) representing the length of each line. Note that \(l_N = 0\) (i.e. the last line is empty).

outputFormat

Output a single integer: the minimum number of key presses required to move the cursor from \((s_l, s_c)\) to \((e_l, e_c)\). If it is impossible to reach the target, output -1.

sample

3 1 1 1 5
4 6 0

4