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:
$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 |