# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You are participating in the Annual Sports of KUET this year.

In an event, you have to jump over `$n$`

pillars. But, the Annual Sports Committee set the pillar heights `$a_i$`

randomly. As you are not an athlete it’s very difficult to jump over all the pillars from the `$1^{st}$`

pillar to the `$n^{th}$`

pillar separately. Fortunately, you are a problem solver! So, you have made a plan. You can perform the following operation any number of times:

- Choose a pillar
`$i$`

and a**positive**integer`$x$`

. Increase the pillar height`$a_i$`

by`$x$`

.**This operation costs**`$x$`

.

With the above operation, you want to make the arrangement of the pillars in such a way to satisfy the following properties:

`$a_1 < a_2 < ... < a_{i-1} < a_i > a_{i+1} > ... > a_{n-1} > a_n$`

for any`$1 < i < n$`

. In words, the first part of the array must be strictly increasing and the last part of the array must be strictly decreasing.`$a_i = h$`

.`$h$`

is the highest height you can jump and you want to make`$a_i$`

equal to this height just to show off your ability!**So, the height of the highest pillar must be equal to**.`$h$`

Thus, you can make a big jump of height `$h$`

and cross all the pillars at once time! But you wonder **what is the minimum cost to do this or is this even possible**.

The first line contains two integers `$n$`

`$(3 \leq n \leq 5\cdot10^{5})$`

and `$h$`

`$(1 \leq h \leq 10^{9})$`

, denoting the number of pillars and the height of the highest pillar you want to make after the arrangement.

The second line contains `$n$`

integers `$a_1, a_2, ..., a_n$`

`$(1 \leq a_i \leq 10^{9})$`

.

In a single line, output should be a single integer which is the minimum cost to make the arrangement or `$-1$`

if it is impossible to make such an arrangement

Input | Output |
---|---|

3 10 3 5 4 | 5 |

Input | Output |
---|---|

5 5 4 3 5 1 2 | -1 |

70% Solution Ratio

Fizzz_83Earliest,

prodip_bsmrstuFastest, 0.0s

riyad000Lightest, 4.2 MB

Sumaya_1703110Shortest, 752B

Login to submit

Prerequisites: Constructive Algorithm, Implementation At first, as you cannot make $a_1$ or $a_n$ t...