Editor Distance

Interview

Time limit2sMemory limit512 MB

Summary

Given the character counts of N lines up to 80 wide, find the fewest arrow-key presses to move a cursor from a start position to a finish position, where vertical moves clamp to each line's end.

Level: Medium7 of 10
Topics: Graph, Shortest path, Dynamic programming, Implementation
Solved: No attempts yet

Problem

You are editing a program in a text editor and want to move the cursor from one position to another using as few key presses as possible.

The editor behaves as follows:

The cursor is moved with the four arrow keys: up (↑), down (↓), left (←), and right (→).
Pressing → moves the cursor one character to the right. If the cursor is on the rightmost character of a line, it moves to the first character of the line below. The cursor does not move if it is already at the bottom-right position.
Pressing ← moves the cursor one character to the left. If the cursor is on the leftmost character of a line, it moves to the last character of the line above. The cursor does not move if it is already at the top-left position.
Pressing ↑ moves the cursor to the character directly above it. If there is no character directly above (the line above is shorter), it moves to the last character of the line above. The cursor does not move if it is already on the first line.
Pressing ↓ moves the cursor to the character directly below it. If there is no character directly below (the line below is shorter), it moves to the last character of the line below. The cursor does not move if it is already on the last line.

Given the number of characters on each line together with a start and a finish position, find the minimum number of key presses needed to move the cursor from the start position to the finish position.

Input

The first line contains $N$ , the number of lines in the program ( $1 \le N \le 100000$ ).

Each of the next $N$ lines contains one integer: the number of characters on that line. Every line has at least $1$ and at most $80$ characters.

The next line contains two integers $R_S$ $C_S$ , the starting row and column of the cursor, where $1 \le R_S \le N$ and $C_S$ is at most the number of characters on row $R_S$ .

The last line contains two integers $R_F$ $C_F$ , the finishing row and column of the cursor, where $1 \le R_F \le N$ and $C_F$ is at most the number of characters on row $R_F$ .

Output

Output a single integer: the minimum number of key presses required to move the cursor from row $R_S$ , column $C_S$ to row $R_F$ , column $C_F$ .

Examples3

Example 1
Input
```
4
40
10
4
80
4 78
1 35
```
Expected output
```
10
```
Example 2
Input
```
1
1
1 1
1 1
```
Expected output
```
0
```
Example 3
Input
```
1
7
1 1
1 7
```
Expected output
```
6
```