14233번 - 악덕 사장

문제

남규회사를 운영하는 사장 zych는 직원들을 부려먹는 걸로 유명하다. 오늘도 zych는 직원들을 부려먹기 위해 고민을 하고 있다.

회사에 들어온 일들은 n개가 있고 각 일들의 마감기한이 있다. 일을 못하면 계약금을 물어야하기 때문에 모든 일을 해야 한다. 하지만 너무 적은 시간을 들이면 퀄리티가 낮아지므로 직원들을 굴려서 최대한 많은 시간을 일을 하게 하려한다. 하지만 또 일마다 시간이 다르면 직원들이 혼동을 하기에, 모든 일을 딱 k시간만 일을 하게 하려한다.

일들의 마감기한이 주어졌을 때, 모든 일을 하면서 k가 최대가 되는 값을 출력하시오.

입력

첫째 줄에는 일의 개수 n이 주어진다.(1≤n≤50,000)

둘째 줄에는 각 일별로 마감기한 Ai가 주어진다.(1≤Ai≤1,000,000,000) 마감기한이 같은 입력은 들어오지 않는다.

출력

모든 일을 다 할 수 있는 일의 기한 최대 k를 출력하시오.

제한

힌트