AKVDHN03 - Kyle Types Text 425 Points

Kyle is writing something on a text editor. He wonders what should be the minimum number of times he needs to press the keys to move the cursor from one point to another point.

Kyle has written “N” number of lines. The i-th line contains Ai characters (including spaces). Obviously if a line contains “Ai” characters, then there can be “Ai + 1” positions where the cursor can be present. Therefore, the cursor’s position can be represented by a pair of integers (x, y), where x is the line number and y is the cursor’s position in that line (positions are indexed starting from one from the start of line).

Kyle only uses “UP”, “DOWN”, “RIGHT” and “LEFT” keys to move the cursor. Let us assume that initially the cursor was at position (x, y), then if Kyle presses any of these keys then:

  • “UP” – if cursor was at x=1, then it does not move. Otherwise it moves to the previous line (with number x-1), to the same y position. But if the line x-1 was shorter than the line x, then the cursor moves to the last position of the line x-1.
  • “DOWN” – if cursor was at x=n, then it does not move. Otherwise it moves to the next line (with number x+1), to the same y position. But if the line x+1 was shorter than the line x, then the cursor moves to the last position of the line x+1.
  • “RIGHT” – If cursor is at the end position of the line x, it does not move, otherwise it moves to position y+1 in the line x.
  • “LEFT” – if cursor is at the starting position of the line x, it does not move, otherwise it moves to position y-1 in the line x.

Kyle will tell you the number of lines he has written and the number of characters written in each line of this file. Find the minimum number of times Kyle should press the keys to move the cursor from position (x1, y1) to position (x2, y2).

Input

First line will contain the integer “N”, the number of lines in the file. The Second line contains “N” integers (A1, A2 ... AN). The third line will contain four integers X1, Y1, X2, Y2.

Output

Print a single integer denoting the minimum number of times Kyle needs to press the keys to move the cursor from the position X1, Y1 to X2, Y2.

Constraints

1 <= N <= 100

0 <= Ai <= 10^5

1 <= X1, X2 <= N

Y1 and Y2 will be in limits according the corresponding X1 and X2.

Example

Input:
4
2 1 6 4
3 4 4 2

Output:
3
Input:
4
10 5 6 4
1 11 4 2

Output:
6
Input:
3
10 1 10
1 10 1 1

Output:
3

Added by:Ankit Kumar Vats
Date:2013-08-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.