Problem H
Heating Up
The spiciness of each slice is measured in Scoville Heat Units (SHU). Jonas has a certain spiciness tolerance, also measured in SHU, which corresponds to the spiciness of the spiciest slice that Jonas can tolerate eating. He has also noticed that, after eating a slice of $k$ SHU, his tolerance immediately increases by $k$.
In order to win the contest, Jonas would like to finish all the slices of his pizza. Help him determine the minimum initial spiciness tolerance necessary to do so while abiding by the contest rules.
Input
The input consists of:
-
One line with an integer $n$ ($3 \le n \le 5 \cdot 10^{5}$), the number of pizza slices.
-
One line with $n$ integers $s_{1}, s_{2}, \ldots , s_{n}$ ($0 \le s_{i} \le 10^{13}$), where $s_ i$ is the spiciness of the $i$th slice in SHU.
Output
Output the minimum initial spiciness tolerance in SHU that Jonas needs in order to be able to eat all slices of the pizza.
Sample Input 1 | Sample Output 1 |
---|---|
5 5 0 10 6 1 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
7 20 23 7 2 3 7 1 |
2 |