Mountain Trek Route#7489
In the Almaty countryside, a mountain cycling trek route (a route with a start and finish at one point) has been constructed. We simulate the route as steps (stairs) of equal width, where each -th step is horizontal and has sea level height a_i meters. Heights of adjacent steps may be equal. The difficulty of the route is the sum of ascents and descents, calculated as:
The originally constructed route turned out to be too difficult for tourists. To simplify it, you can use blocks. Each block has the same width as a step and a height of meter. Any block can be placed on any step or on a previously placed block, or not used at all.
What is the maximum possible decrease in the route's difficulty?
The first line contains the numbers (2 \le n \le 10^6) and (1 \le k \le 10^9). The next line contains non-negative integers, each representing the height of a step.
Print one number — the maximum possible decrease in the route's difficulty.
Example 1
Example 2
Example 3