소프트빌의 입문 프로그램

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

요약

주어진 일수마다 하루에 한 줄씩 더 쓰는 규칙으로 만들 수 있는 가장 짧은 프로그램 길이를 구합니다.

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

문제

소프트빌 마을에서는 소프트웨어를 정해진 방식으로 만든다. 첫날에는 코드를 한 줄 이상 쓰고, 다음 날부터는 매일 전날보다 정확히 한 줄씩 더 쓴다.

소프트빌 주민은 열 살이 지나면 아주 복잡한 프로그램 하나를 처음부터 직접 작성하는 입문 과정을 거쳐야 한다. 이 프로그램의 코드는 모든 주민에게 똑같고 줄 수는 정확히 $N$ 이다. 프로그램을 끝내는 데 걸린 날수는 주민마다 다를 수 있지만, 매일 전날보다 한 줄 더 쓴다는 규칙은 누구나 지킨다.

주민들이 입문 프로그램을 쓰는 데 며칠씩 걸렸는지 주어진다. 가능한 $N$ 중 가장 작은 값을 구하라. 프로그램은 비어 있지 않으므로 $N$ 은 1 이상이다.

입력

첫째 줄에 소프트빌 주민의 수 $m$ 이 주어진다 ( $0 \le m \le 1000$ ). 둘째 줄에 각 주민이 입문 프로그램을 쓰는 데 걸린 날수가 공백으로 구분되어 $m$ 개 주어진다. 날수는 모두 $2^{63}$ 보다 작은 양의 정수이다. $m = 0$ 이면 둘째 줄은 비어 있다.

출력

첫째 줄에 가능한 $N$ 중 가장 작은 값을 출력한다. 어떤 $N$ 을 골라도 주어진 날수를 모두 만족시킬 수 없으면 0을 출력한다. 답이 존재하면 그 값은 $2^{63}$ 보다 작다. $m = 0$ 이면 1을 출력한다.

예제5

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