Show Off!

Muhimin_Osim Intra KUET Programming Co...
Limits 1s, 256 MB

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.

Input

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})$.

Output

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

Samples

InputOutput
3 10
3 5 4
5
InputOutput
5 5
4 3 5 1 2
-1

Submit

Login to submit.

Statistics

75% Solution Ratio
Fizzz_83Earliest, Jul '20
prodip_bsmrstuFastest, 0.0s
riyad000Lightest, 4.2 MB
Sumaya_1703110Shortest, 752B
Toph uses cookies. By continuing you agree to our Cookie Policy.