Problem C
Thanos the Hero
Thanos, as we all know, is the beloved character from a popular movie franchise who is a misunderstood hero and totally not a villain at all. Also, his favorite hobby is intergalactic mass genocide.
It is not Thanos’s goal to kill everyone in the entire universe – that’d make him a villain. Instead, Thanos is the hero that tries to create the perfect universe by reducing each world to what he believes is an appropriate population.
Thanos goes by one rule: For any two worlds $X$, $Y$, if Thanos prefers $X$ to $Y$, then $X$’s population must be strictly greater than $Y$’s.
There are in total $N$ worlds in the universe, and Thanos has a strict total ordering of these worlds based on his preference. When Thanos’s rule is fulfilled on his ordering, the universe is perfect.
Thanos is now ready to go on a massive killing spree to create the perfect universe. At the same time, Thanos wants to minimize the number of lives he has to take; that is right, they call him “Thanos the merciful”, and totally not because he’s too lazy to kill more than he has to.
Given the ordering of Thanos’s preference of worlds and each world’s population, Thanos wants your help to determine how many lives he has to take exactly.
Input
The first line contains a single integer $N$ $(1\leq N\leq 50\, 000)$.
The next line contains $N$ integers separated by single spaces ($1\leq a_ i\leq 10^9$), $a_ i$ represents the population of the $i$-th world. Thanos prefers the $i+1$-st world to the $i$-th world.
Output
One number which represents the number of lives Thanos takes today. If it is impossible to create the perfect universe, output $1$ (Thanos kills himself).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 2 3 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 0 0 1 |
1 |
