악덕 사장

남규회사를 운영하는 사장 zych는 직원을 혹독하게 부리기로 유명하다. 오늘도 zych는 직원을 어떻게 더 굴릴지 궁리하고 있다.

회사에 들어온 일은 $n$개이고, 일마다 마감 기한이 정해져 있다. 기한을 넘기면 계약금을 물어야 하므로 $n$개를 모두 끝내야 한다. 그런데 한 일에 너무 적은 시간을 들이면 결과물의 품질이 떨어지기 때문에 zych는 직원이 일하는 시간을 최대한 늘리려 한다. 일마다 걸리는 시간이 다르면 직원이 혼란스러워하므로, 모든 일에 정확히 $k$시간씩 쓰게 한다.

일은 시각 $0$에 시작해서 한 번에 하나씩, 쉬는 구간 없이 이어서 처리한다. 마감 기한이 $A_i$인 일은 시각 $A_i$ 이하에서 끝나야 한다. 일을 처리하는 순서는 마음대로 정한다.

$n$개의 마감 기한이 주어질 때, 모든 일을 기한 안에 끝낼 수 있는 가장 큰 정수 $k$를 출력하시오.

첫째 줄에 일의 개수 $n$이 주어진다. ($1 \le n \le 50000$)

둘째 줄에 일별 마감 기한 $A_1, A_2, \dots, A_n$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 1000000000$) 마감 기한이 같은 일은 들어오지 않는다.

첫째 줄에 모든 일을 기한 안에 끝낼 수 있는 가장 큰 정수 $k$를 출력한다.