문제
철기는 배가 지나다니는 항구 옆의 작은 마을에 살고 있다. 그런데 항구를 방문해 왔던 배들이 어느 날 항구를 모두 방문했다.철기는 이를 보았고, 이 날을 1일로 지정했다. 그 후, 여태까지 많은 날이 지나 갔나갔고, 철기는 하나 이상의 배가 항구를 방문했던 날을 빠짐없이 기록했다. 이런 날을 '좋은 날'이라 한다. 게다가, 철기는 각 배가 항구를 일정한 간격을 주기로 방문한다는 것을 알아냈다.
예를 들면 3일의 간격으로 오는 배는 1,4,7,10,... 일에 방문한다는 말이다. 철기의 좋은 날 리스트가 주어졌을 때, 항구에 방문한 배의 수가 최소가 되게 계산하여라.
입력
입력의 첫 번째 줄에는 좋은 날의 수 N(2≤N≤5000)이 입력된다.
다음은 N줄에 걸쳐 좋은 날이 오름차순으로 입력된다. 좋은 날의 시작은 항상 1이며, 마지막은 109을 넘지 않는다.
입력의 70%는 좋은 날이 5,000,000을 넘지 않는다.
출력
가능한 최소의 배의 수를 출력한다.
예제 #1
3
1
3
4
2
예제 #2
5
1
7
10
13
19
2
예제 #3
3
1
55000
999999999
1
출처
COCI 2010/2011 contest5 3
로그인해야 코드를 작성할 수 있어요.