NPC2015F - Eefun and Doors

no tags 

Eefun is a nomad who like to explore dungeons. On each dungeons, there's a valuable treasure waiting for him. However, Eefun should pass some obstacles to get the treasure.

In the dungeon, there are N doors which moves every second. These doors have width equal one and the dungeon has M width. When Eefun enters the dungeon (pass the first door), the timer start and the doors will start moving. The door will move to the right initially. When a door reach the end of the dungeons (at position M), then the door will change direction to left until reaching the leftmost position again (position 1). Eefun knows the initial position of all doors.

To pass a door, Eefun need to have same position with the door and he needs a second to pass a door. If next door has different position with Eefun, he can stay at the current position or move a position to the left or right.

After trying many dungeons, Eefun gets dizzy because he sees moving door everywhere. Therefore, he wants to know the minimum number of seconds to get the treasure. Eefun can obtain the treasure after he pass all the doors. 

Input

First line contains 2 numbers, N and M.
Second line contains N numbers, the initial position of each doors. 

Output

Output a single number, the minimum time Eefun needs to obtain the treasure.

Example

Input 1:
3 5
1 4 3 Output 1: 5 Input 2: 5 5
1 1 1 1 1 Output 2: 18

Explanation

For the first testcase, the initial doors are like picture below:

|P****|

|-----|

|***P*|

|-----|

|**P**| 

First, Eefun will enter the dungeon at time = 1 and the doors will start moving

|*P***|

|E----|

|****P|

|-----|

|***P*|

Then, Eefun will move to the right 2 times

|***P*|

|--E--|

|**P**|

|-----|

|***P*|

Then, Eefun will pass the second door which take one second.

|****P|

|-----|

|*P***|

|--E--|

|**P**|

As Eefun already has same position with the last door, he can continue to the last door and take another second. His minimum time to pass all the doors are 1+2+1+1 = 5 seconds.

Constraints:

  • 1 ≤ Position of each door ≤ M
  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ M ≤ 10.000

hide comments
Arianto Wibowo: 2015-12-25 11:33:36

@Bhargav Golla:
You submit empty plaintext

Bhargav Golla: 2015-10-28 02:22:29

Hi
Could you tell me what is wrong with Submission ID: 15486685? I tested with 1000000 10000 and 1000000 1s as doors, and my result doesn't overflow. Not sure what is wrong with my solution that is making it produce WA. Thanks


Added by:Louis Arianto
Date:2015-10-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:NPC Schematics 2015