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 |