시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 95 53 47 68.116%

문제

해빈이는 배가 한 척이라도 올까 말까 한 작은 항구 마을에 산다. 그런데 어느 날, 마을을 방문한 적이 있는 모든 배가 한꺼번에 마을을 방문한 날이 있었다. 해빈이는 이 날을 기념해 1일로 센다. 그리고 배가 한 척이라도 마을에 온 날을 신나는 날이라고 하고 특별히 리스트에 기록해두었다.

해빈이는 마을에 방문하는 배들을 관찰한 결과, 이들이 일정한 날자 간격을 두고 주기적으로 항구를 방문한다는 사실을 알아차렸다. 예를 들어, 간격이 3인 배는 1일, 4일, 7일, 10일 등에 해빈이의 마을에 온다.

오늘은 신나는 날이다. 오늘을 포함해서 해빈이의 신나는 날 리스트가 주어질 때, 방문한 배의 최소 수를 구하라. (해빈이는 모든 신나는 날을 리스트에 정확히 적어두었다. 따라서 항상 답이 존재한다.)

입력

입력의 첫 줄에 정수 신나는 날의 갯수 N (2 ≤ N ≤ 5000)이 주어진다.

다음 N줄에는 신나는 날의 번호가 오름차순으로 한 줄에 하나 씩 주어진다. 첫 번째 수와 마지막 수는 각각 해빈이가 관찰을 시작한 날, 그리고 해빈이가 매긴 오늘의 번호이다. 즉, 첫 번째 줄은 항상 1이다. 마지막 수(오늘의 번호)는 10^9보다 작다.

출력

가능한 배의 최소 수를 출력한다.

예제 입력

3
1
3
4

예제 출력

2

힌트