Problem A
Ego Boosting
Languages
en
sv
After several years of grinding programming, Tommy has realized that he is not confident at all.
To fix this, Tommy would like to boost his ego!
Initially, Tommy has $E$ ego.
There are $N$ ego-increasing-problems (EP for short), where solving any of the EP will increase Tommy’s ego by 1. Each EP has a label which is a unique integer from $1$ to $N$, and a difficulty rating $a_i$.
To guarantee that Tommy solves an EP, Tommy must have at least the same amount of ego as the difficulty of the EP. In other words, $E \geq a_i$ must be satisfied for Tommy to be able to solve the $i$’th EP.
The first EP that Tommy chooses to solve could be any of the $N$ problems. But after solving an EP labeled $x$, he can only choose to attempt either
-
The unsolved EP with the largest label less than $x$, or
-
The unsolved EP with the smallest label greater than $x$.
At any time during his ego-increasing journey, Tommy can eat an ego-cookie to increase his ego by 1 unit.
What is the minimum number of ego-cookies Tommy has to eat to be able to solve all EPs?
Input
The first line contains two integers, $N$ $(1 \leq N \leq 5 \cdot 10^5)$ and $E$ $(0 \leq E \leq 10^9)$.
The second line contains $N$ integers, $a_i$ $(1 \leq a_i \leq 10^9)$ for $i = 1,\dots ,N$, where the difficulty of the EP labeled $i$ is $a_i$.
Output
Print an integer: the minimum number of ego-cookies Tommy has to eat to be able to solve all EPs.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$7$ |
$N \leq 3$ |
|
$2$ |
$12$ |
$N \leq 15$ |
|
$3$ |
$23$ |
$N \leq 5000$ |
|
$4$ |
$17$ |
There are at most 2 distinct integers in $a_1, \dots , a_N$. |
|
$5$ |
$41$ |
No additional constraints. |
Explanation of Samples
If we solve the EPs in the order $a_4, a_5, a_3, a_2, a_1, a_6$, the process is as follows:
-
Before solving $a_4 = 2$, Tommy eats 1 cookie to increase his ego to 2. After solving the EP, his ego becomes 3.
-
For $a_5 = 3$, Tommy’s ego is already 3, so he solves it without eating a cookie. His ego increases to 4.
-
Before solving $a_3 = 7$, Tommy eats 3 cookies to raise his ego to 7. After solving the EP, his ego becomes 8.
-
For $a_2 = 4$, Tommy’s ego is 8 (no cookies needed). After solving it, his ego becomes 9.
-
For $a_1 = 9$, Tommy solves it directly. His ego increases to 10.
-
Finally, for $a_6 = 10$, Tommy solves it with his current ego of 10. His ego becomes 11.
In total, Tommy eats 4 cookies, which is the minimum number required to solve all EPs.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 1 9 4 7 2 3 10 |
4 |