#1793 항구

35  1 s   128 MB  

Description

성진이 배가 지나다니는 항구 옆의 작은 마을에 살고있다.

어느날 지금까지 항구를 방문해 왔던 모든 배들이 항구를 방문했다. 성진이 이를 보았고, 이 날을 1일로 지정했다.

그 후, 많은 날이 지나 갔났고, 성진이는 하나 이상의 배가 항구를 방문했던 날을 빠짐없이 기록했다.

이런 날을 '좋은 날'이라 한다. 게다가, 성진이는 각 배가 항구를 일정한 간격을 주기로 방문한다는 것을 알아냈다.

예를 들면 3일의 간격으로 오는 배는 1,4,7,9,... 일에 방문한다는 말이다. 성진이의 좋은 날 리스트가 주어졌을 때, 이에 맞게 배들이 항구에 방문할 때의 최수가 되는 경우를 구하는 프로그램을 작성하라.

Input

입력의 첫 번째줄에는 좋은 날의 수 N(2≤N≤5000)이 입력된다.

다음은 N줄에 걸쳐 좋은 날이 오름차순으로 입력된다.

좋은 날의 시작은 항상 1이며, 마지막은 109을 넘지 않는다. 

Output

조건을 만족 할 때 항구를 방문하는 최소 배의 수를 출력한다.

Sample Input

Sample Output

3
1
3
4
2

Sample Input 2

5
1
7
10
13
19

Sample Output 2

2

Sample Input 3

3
1
500000000
999999999

Sample Output 3

1