200792: [AtCoder]ARC079 E - Decrease (Judge ver.)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

We have a sequence of length $N$ consisting of non-negative integers. Consider performing the following operation on this sequence until the largest element in this sequence becomes $N-1$ or smaller. (The operation is the same as the one in Problem D.)

  • Determine the largest element in the sequence (if there is more than one, choose one). Decrease the value of this element by $N$, and increase each of the other elements by $1$.

It can be proved that the largest element in the sequence becomes $N-1$ or smaller after a finite number of operations.

You are given the sequence $a_i$. Find the number of times we will perform the above operation.

Constraints

  • $2 ≤ N ≤ 50$
  • $0 ≤ a_i ≤ 10^{16} + 1000$

Input

Input is given from Standard Input in the following format:

$N$
$a_1$ $a_2$ ... $a_N$

Output

Print the number of times the operation will be performed.


Sample Input 1

4
3 3 3 3

Sample Output 1

0

Sample Input 2

3
1 0 3

Sample Output 2

1

Sample Input 3

2
2 2

Sample Output 3

2

Sample Input 4

7
27 0 0 0 0 0 0

Sample Output 4

3

Sample Input 5

10
1000 193 256 777 0 1 1192 1234567891011 48 425

Sample Output 5

1234567894848

Input

题意翻译

给你 $n$ 个数,每次操作可以取 $n$ 个数中的最大值减掉 $n$,但会使其它所有数增加 $1$。如果有多个最大值,只能够选择一个减掉。 询问最少需要多少次操作使得所有数都小于 $n$。 Translated by @[Zealous_YH](https://www.luogu.com.cn/user/399150)

加入题单

上一题 下一题 算法标签: