有一天n个朋友聚在一起玩《黑手党》。在每轮游戏中,必须有一名玩家担任监督员,其他 n-1 人参与游戏。对于每个人,我们知道他想在多少轮中成为玩家,而不是监督者:第 i 个人想玩人工智能轮。他们需要玩“黑手党”游戏的最少轮数是多少,才能让每个人至少玩他们想要玩的轮数?
输入
第一行包含整数 n (3 ≤ n ≤ 105)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 列表中的第 i 个数字是第 i 个人想要玩的轮数。
输出
在一行中打印一个整数 - 朋友们需要让第 i 个人玩至少 ai 轮的最小游戏轮数。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
3 3 2 2
输出 #1
4
输入 #2
4 2 2 2 2
输出 #2
3
注意
你不需要了解“黑手党”的规则来解决这个问题。如果您好奇,这是俄罗斯从苏联时代获得的游戏:http://en.wikipedia.org/wiki/Mafia_(party_game)。