There is a line of boxes on a table, indexed from to . Each box is assigned a number between and such that every number from to appears at least once. In order to open a box with , you must have already opened a box with . You do not need to open anything before opening a box with .
In addition, to get from index to index , you need to travel a distance of . You are initially at index , and all the boxes are closed. What is the minimum distance you need to travel in order to open a box with ?
Constraints
For all subtasks:
- There is always at least one box with for all .
Points Awarded | |
---|---|
5 points | |
10 points |
Input Specification
The first line contains two integers and .
The second line contains integers .
Output Specification
Output the minimum distance required. Please note that this number may not fit inside a 32-bit integer.
Sample Input
4 3
3 1 2 2
Sample Output
5
Explanation for Sample Output
Starting from index , we go to index , then to index and then back to index . The total distance travelled is . It can be shown that this is the minimal distance required.
Comments