풍선 부풀리기

NWERC 2018을 맞아 주최진은 풍선에 특별한 준비를 했다. 크기가 같은 풍선을 사는 대신, 1부터 n까지의 모든 정수 크기의 풍선을 하나씩 샀다. 크기 s인 풍선의 용량은 s 데시리터이다.

풍선을 손으로 부풀리는 일을 피하기 위해, 주최진은 헬륨 가스통도 n개 샀다. 각 가스통은 풍선 하나를 부풀리는 데에만 쓸 수 있고, 그 풍선에 전부 비워 넣어야 한다. 가스통을 완전히 사용하기 전에 풍선에서 분리할 수는 없다.

안타깝게도 가스통은 벼룩시장에서 산 것이라 들어 있는 헬륨의 양이 제각각일 수 있다. 어떤 것은 비어 있을 수도 있다. 이 까다로운 상황을 최대한 잘 헤쳐 나가려면 가스통을 풍선에 영리하게 짝지어야 한다.

주최진은 모든 가스통을 서로 다른 풍선에 배정하되, 용량에 비해 가장 적게 부풀려진 풍선에 들어 있는 헬륨의 비율이 최대가 되게 하려고 한다. 이렇게 할 때 가능한 (최소 비율의) 최댓값은 얼마인가?

용량을 넘겨 부풀린 풍선은 터진다. 터지는 일은 좋지 않으니 반드시 피해야 한다.

입력은 다음과 같이 주어진다.

• 풍선과 가스통의 개수 n (1 ≤ n ≤ 2 · 105)이 적힌 한 줄.
• n개의 정수 c1, . . . , cn (각 i에 대해 0 ≤ ci ≤ n)이 적힌 한 줄. 가스통에 든 헬륨의 양을 데시리터 단위로 나타낸다.

모든 풍선을 터뜨리지 않고 부풀릴 수 있으면, 모든 풍선을 용량의 최소 f 비율까지 부풀릴 수 있는 최대 비율 f를 출력한다. 그렇지 않으면 “impossible”을 출력한다.

답의 절대 오차 또는 상대 오차는 10−6 이하여야 한다.