미코는 항구에 접한 조그마한 마을에 산다:

미코는 항구를 방문하는 모든 배가 언제 나타날지를 안다. 이 날을 인덱스1 로 나타낸다.

시간이 흐른 후 적어도 하나의 배가 항구에 오는 날을 기록했다. 그는 이 날을 재미있는 날로 명명 한다.

또한 , 미코는 모든 배들이 항구에 일정한 주기로 방문하는 것을 알았다.

예를 들어, 3 일을 주기로 한다면 항구에 1 , 4 , 7 ,10, ... 날 방문 한다는 것이다.

미코의 즐거운 날의 리스트가 주어질 때 항구에 도착 가능한 최소 배를 구하는 것이 문제이다.

답이 존재하는 것은 보장된다.

입력

• 첫 수는 즐거운 날 수로 정수 N (2 ≤ N ≤ 5000)으로 주어진다.
• 다음 N 줄은 즐거운 날의 인덱스 한줄에 하나씩 오름차순으로 나타낸다.

출력

입출력 예

입력

3
1
3
4

출력

2

입력

5
1
7
10
13
19

출력

2

입력

3
1
500000000
999999999

출력

1

입출력 보충

• 하나의 배가 주기 9 으로 항구에 온다면 1 10 19
• 다른 하나의 배가 주기 6 으로 항구에 온다면 1 7 13

출처:coci 2011