P15400 [NOISG 2026 Prelim] Hungry Cats

In the kingdom of cannibalistic cats, Ket the cat has just been informed that National Cat Day (NCD) will be held tomorrow. As the appointed software engineer, he is tasked with developing a system to report on the cannibalism situation. There are $n$ cats joining the NCD celebration, numbered from 1 to $n$. The $i$-th cat has a happiness level of $h[i]$. At any point in time, a cat may eat a **strictly** less happy cat. After this happens, the happier cat’s happiness level **increases by $1$** and it is **no longer able to eat any other cats**. In addition, the less happy cat vanishes. Ket is tasked with determining whether it is possible for only one cat to be left at the end of the celebration. This means that all other cats were eaten.

Your program must read from standard input. The first line of input contains an integer $n$. The second line of input contains $n$ space-separated integers $h[1], h[2], \ldots, h[n]$.

Your program must print to standard output. Output **YES** if it is possible for only one cat to be left after the celebration, or **NO** otherwise.

### Sample Test Case 2 Explanation There are $n = 3$ cats with hunger levels $31$, $41$, and $59$. It is possible for one cat to be left after the celebration if the second cat eats the first cat and subsequently gets eaten by the third cat. ### Sample Test Case 3 Explanation It is impossible for the cats to eat each other in a way that leaves one cat remaining at the end of the celebration. ### Subtasks For all test cases, the input will satisfy the following bounds: - $2 \le n \le 200\,000$ - $0 \le h[i] \le 10^9$ for all $1 \le i \le n$ Your program will be tested on input instances that satisfy the following restrictions: | Subtask | Score | Additional Constraints | |:-------:|:-----:|:-------------------------------------------:| | 0 | 0 | Sample test cases | | 1 | 8 | $n = 2$ | | 2 | 10 | $n \le 3$ | | 3 | 6 | $h[1] = h[n]$ | | 4 | 18 | $n \le 1000$ | | 5 | 28 | $h$ is non-decreasing ($h[i] \le h[i+1]$ for all $1 \le i \le n-1$) | | 6 | 30 | No additional constraints |