시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 135 28 24 32.877%

문제

공 포장하기 문제와 다르게 이 문제의 색의 종류는 총 K가지이다. 색은 1부터 K까지 정수로 나타내며, 색이 i인 공의 개수는 X[i]개이다.

오늘은 이 공을 박스로 포장하려고 한다. 박스에는 공이 최대 K개까지 들어갈 수 있다.

박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다.

필요한 박스 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 색의 개수 K가 주어진다. (1 ≤ K ≤ 100,000)

둘째 줄에는 각각의 색을 가지는 공의 개수 X[i]가 주어진다. (1 ≤ X[i] ≤ 1,000,000,000)

출력

첫째 줄에 필요한 박스의 최소 개수를 출력한다.

예제 입력 1

3
4 2 4

예제 출력 1

4

예제 입력 2

1
58

예제 출력 2

58

예제 입력 3

7
1 6 6 6 6 6 6

예제 출력 3

6

예제 입력 4

5
5 3 5 3 5

예제 출력 4

5

출처