A. Мафия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Как-то раз собрались n друзей, чтобы сыграть в «Мафию». В каждом раунде игры «Мафия» должен быть назначен ведущий (кто-то один из ребят), остальные n - 1 человек принимают участие в игре. Для каждого человека известно, в каком количестве раундов он хочет принять участие как игрок, а не как ведущий: i-ый человек хочет сыграть ai раундов. Какое минимальное количество раундов игры «Мафия» нужно сыграть, чтобы каждый человек сыграл как минимум столько раундов, сколько хочет?

Входные данные

В первой строке записано целое число n (3 ≤ n ≤ 105). Во второй строке через пробел записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — i-ое число в списке обозначает количество раундов, которое хочет сыграть i-ый человек.

Выходные данные

В единственную строку выведите целое число — минимальное количество раундов игры, которое нужно сыграть, чтобы i-ый человек сыграл как минимум ai раундов.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3
3 2 2
Выходные данные
4
Входные данные
4
2 2 2 2
Выходные данные
3