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.


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


3 10
3 5 4
5 5
4 3 5 1 2



    70% Solution Ratio

    Fizzz_83Earliest, 2w ago

    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...