아이템 배치하기

시간 제한1초메모리 제한256 MB

요약

N개의 아이템을 원형으로 배치할 때, 각 아이템이 자신부터 시계 방향으로 A_i개의 아이템을 강화한다고 하자. 강화되는 아이템 수가 최소가 되도록 배치하고 그 최솟값을 출력한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

최근 싸이컴에서 제작한 게임 '입부 전쟁'에서는 다양한 아이템을 활용해 전쟁의 승리 확률을 높일 수 있습니다. 아이템은 한 번에 $N$ 개씩 강화할 수 있습니다.

강화력이 각각 $A_1, A_2, \cdots, A_N$ 인 $N$ 개의 아이템을 강화하려고 할 때, 아이템을 강화하는 방법은 다음과 같습니다.

$N$ 개의 아이템을 적절한 순서로 원형으로 배열합니다.
$i$ 번 아이템은 자신부터 시작해 시계 방향으로 $A_i$ 개의 아이템을 강화시킵니다. $A_i=0$ 인 아이템은 다른 아이템에게 아무 영향도 주지 않습니다.
위 규칙에 따라 여러 번 강화되는 아이템이 있더라도 실제로는 한 번만 강화됩니다.

브루는 '입부 전쟁' 세계 1위를 기록한 흑왕을 이기기 위해 아이템을 강화하려고 합니다. 하지만 브루는 어떻게 배치해야 최대한 많은 아이템을 강화할 수 있을지 찾지 못했고, 당신에게 도움을 요청했습니다. 그러나 당신도 '입부 전쟁' 게임을 열정적으로 하는 플레이어이기 때문에 브루의 아이템 강화를 방해하려고 합니다. 따라서 당신은 브루의 부탁대로 가장 많은 아이템을 강화하게 하는 대신, 가장 적은 아이템을 강화시키는 방법을 찾으려고 합니다.

$N$ 개의 아이템과 각각의 강화력 $A_1, A_2, \cdots, A_N$ 이 주어졌을 때, 최대한 적은 아이템만 강화되게 하고, 그때 강화되는 아이템의 수를 구해 출력하세요.

입력

첫 줄에는 아이템의 수를 나타내는 정수 $N$ 이 주어집니다.

둘째 줄에는 각 아이템의 강화력을 나타내는 정수 $A_1, A_2, \cdots, A_N$ 이 주어집니다.

출력

가능한 모든 아이템 배치들 중에서, 강화되는 아이템 수의 최솟값을 출력합니다.

제한

$1 \le N \le 5 \times 10^5$
$0 \le A_i \le N$

예제2

예제 1
입력
```
3
2 0 1
```
예상 출력
```
2
```
예제 2
입력
```
5
2 1 2 1 2
```
예상 출력
```
5
```