Duck Button Game

Background

Shor the Duck is playing a game with his friends on a one-dimensional grid consisting of $n$ cells numbered from 1 to $n$ left to right.

Problem Description

Each cell has a button. If at any time there are at least $a[i]$ ducks on cell $i$, the button on that cell becomes permanently pressed. Even if those ducks leave, the button remains pressed. To win the game, all $n$ buttons must be pressed.

Initially, there are $d$ ducks on cell 1. In each move, one duck can move one cell to the left or to the right.

Determine the minimum total number of moves required to win the game. It is guaranteed that a solution exists.

Input Format

The input is given from standard input as follows:

$n$ $d$ $a[1]\;a[2]\;...\;a[n]$

Output Format

Output a single integer: the minimum total number of moves needed to win the game.

Sample

2 199
175 42

42

5 3
1 1 0 1 0

3

5 7
2 2 2 2 2

8

7 5
1 3 3 4 5 5 5

30

8 9
7 6 6 6 3 3 3 1

28

8 5
2 3 5 1 4 2 1 0

21

4 1000000000
1 1 1 999999999

2999999997

Constraints

• For all test cases:

  $1 \le n \le 200000$ $1 \le d \le 10^{9}$ $0 \le a[i] \le 10^{9}$ It is guaranteed that a solution exists.

• Subtasks:

  Subtask	Score	Special Property
  1	8	$n=2$
  2	5	$a[i]=0$
  3	11	$a[i]\le 1$
  4	6	All $a[i]$ equal
  5	19	$n,d\le 1000$
  6	12	$a[i]$ is non-decreasing
  7	16	$a[i]$ is non-increasing
  8	23	None