Даниэль наблюдает за игрой футбольной команды во время тренировки. Во время этой тренировки они хотят улучшить свои навыки паса.
В игре участвуют \(n\) игроков, которые делают передачи друг другу. Тренировка закончилась, но к сожалению, поскольку мячи двигались слишком быстро, Даниэль не смог понять, сколько мячей находилось в игре. Единственное, что он знает, это количество пасов, сделанных каждым игроком за время тренировки.
Найдите минимально возможное количество мячей, которые участвовали в игре.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
Примечание
В первом наборе входных данных с единственным мячом игра могла проходить так:
\(2 \rightarrow 1 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 2\).
Во втором наборе входных данных выполнить передачи одним мячом невозможно. Один из возможных способов игры двумя мячами:
\(2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1\).
\(2 \rightarrow 3 \rightarrow 2 \rightarrow 1\)
В третьем наборе пасов не было, поэтому возможны \(0\) мячей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
2 3 3 2
3
1 5 2
2
0 0
4
1000000000 1000000000 1000000000 1000000000
|
1
2
0
1
|