방문한 배의 최소 수

해빈이는 배가 거의 오지 않는 작은 항구 마을에 산다. 어느 날, 지금까지 마을을 방문한 적이 있는 모든 배가 동시에 들어왔다. 해빈이는 그날을 1일로 정했다.

배가 한 척이라도 마을에 온 날을 신나는 날이라고 하며, 해빈이는 그런 날을 빠짐없이 목록에 기록했다.

관찰 결과, 각 배는 일정한 날짜 간격으로 마을을 방문한다. 예를 들어 간격이 3일인 배는 1일, 4일, 7일, 10일, ...에 마을에 온다.

오늘도 신나는 날이다. 오늘을 포함한 신나는 날 목록이 주어질 때, 이 목록을 만들 수 있는 배의 최소 수를 구하라. 해빈이는 모든 신나는 날을 정확히 기록했으므로 답은 항상 존재한다.

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

다음 N줄에는 신나는 날의 번호가 오름차순으로 한 줄에 하나씩 주어진다. 첫 번째 번호는 항상 1이며, 마지막 번호는 오늘의 번호이다. 오늘의 번호는 10^9보다 작다.

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