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 nn pillars. But, the Annual Sports Committee set the pillar heights aia_i randomly. As you are not an athlete it's very difficult to jump over all the pillars from the 1st1^{st} pillar to the nthn^{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 ii and a positive integer xx. Increase the pillar height aia_i by xx. This operation costs xx.

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

  • a1<a2<...<ai1<ai>ai+1>...>an1>ana_1 < a_2 < ... < a_{i-1} < a_i > a_{i+1} > ... > a_{n-1} > a_n for any 1<i<n1 < 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.

  • ai=ha_i = h. hh is the highest height you can jump and you want to make aia_i equal to this height just to show off your ability! So, the height of the highest pillar must be equal to hh.

Thus, you can make a big jump of height hh 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 nn (3n5105)(3 \leq n \leq 5\cdot10^{5}) and hh (1h109)(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 nn integers a1,a2,...,ana_1, a_2, ..., a_n (1ai109)(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-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


    73% Solution Ratio

    Fizzz_83Earliest, Jul '20

    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 a1a_1a1​ or ana_n...

    Toph uses cookies. By continuing you agree to our Cookie Policy.