Practice on Toph

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

Show Off!

By Muhimin_Osim · 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

    Discussion

    Statistics


    70% Solution Ratio

    Fizzz_83Earliest, 2w ago

    prodip_bsmrstuFastest, 0.0s

    riyad000Lightest, 4.2 MB

    Sumaya_1703110Shortest, 752B

    Submit

    Login to submit

    Editorial

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