Football tournament
Description
$n$ teams train at the sports school. The $i$th team has the strength $a_i$. A month later, a tournament will take place, during which each team will play a match with every other team. The match ends with the victory of one of the teams if it is stronger than the other, or a draw if the strengths of the teams are equal. At the end of the tournament, each team will receive a certain number of points for the matches played: 3 points for each win and 1 point for each draw.
Mr. Yaruta can train with any team, and then its strength will increase by 1. He is interested in the maximum total amount of points of all teams together. What is the minimum number of training session he need to provide to do this?
The first line contains the number of teams $n$, $(2 \leq n \leq 200000)$. The second line contains $n$ space-separated integers $a_i$, $(1 \leq a_i \leq 10^9)$.
Output one integer - the answer to the problem.
Input
The first line contains the number of teams $n$, $(2 \leq n \leq 200000)$. The second line contains $n$ space-separated integers $a_i$, $(1 \leq a_i \leq 10^9)$.
Output
Output one integer - the answer to the problem.
3
6 5 6
1