The Duck Button Press Puzzle

Shor the Duck is playing a game with his friends on a 1-dimensional grid of \(n\) cells numbered from 1 to \(n\). Each cell has a button. The button at cell \(i\) is permanently pressed if at some moment there are at least \(a_i\) ducks on that cell. Once pressed, the button remains pressed even if the ducks leave.

Initially, there are \(d\) ducks on cell 1. In one move, a single duck may move one cell to the left or right. The goal is to press all \(n\) buttons with the minimum total number of moves. It is guaranteed that it is possible to win the game with some number of moves.

Warning for C++ users: The large size of integers involved in this problem may require the use of the long long data type instead of int.

Observation and Hint:

A key observation is that since a duck moving from cell 1 to cell \(i\) must eventually travel a distance of \(i-1\), one strategy is to plan a consolidated group of ducks which moves sequentially from one cell to the next. When the group reaches cell \(i\), its size must be at least \(a_i\) to press the button. However, you may opt to only move as many ducks as needed for future requirements rather than moving all ducks together. In fact, an optimal strategy is to decide, for each cell (starting from cell 2), to move exactly as many ducks as the maximum requirement from that cell to cell \(n\).

Define for every cell \(i\) (with \(2 \le i \le n\)) the value \(R_i = \max\{a_i, a_{i+1}, \dots, a_n\}\). Then the minimum total number of moves required is:

[ \text{Total Moves} = \sum_{i=2}^{n} R_i. ]

Your task is to compute this sum given \(n\), \(d\) and the array \(a\) (where \(a_1, a_2, \dots, a_n\) are given and \(d\) is the initial number of ducks, with \(d \ge a_1\)).

inputFormat

The first line contains two integers \(n\) and \(d\) \((2 \le n \le 10^5,\; 1 \le d \le 10^{12})\) representing the number of cells and the initial number of ducks on cell 1 respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^{12})\) where \(a_i\) is the number of ducks required to press the button at cell \(i\). It is guaranteed that \(d \ge a_1\) and that the game can be won.

outputFormat

Output a single integer, the minimum total number of moves required to press all buttons.

sample

3 10
5 3 4

8