← 返回题目列表

Codeforces · 348/A

A. 黑手党

中文机器翻译题面 查看原题

有一天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)。