Pipelined

현대자동차에서 근무하는 로하는 작업 슬롯 하나로 $N$대의 자동차를 생산하는 공정을 계획하려 한다. $i$번째 자동차를 생산하려면 $s_i$단계의 생산 프로세스를 거쳐야 한다. 작업 슬롯은 수직선 위의 $[0,1)$로 나타낼 수 있으며, $i$번째 자동차의 생산이 진행 중이면 이 중 크기가 $\frac{1}{s_i}$인 반열린 구간을 차지한다. 0초부터 시작하여 1초마다 다음 일이 순서대로 일어난다.

• 먼저 슬롯에 할당된 모든 생산 프로세스가 자신의 크기만큼 뒤로 이동한다. 즉, $i$번째 생산 프로세스가 $[\frac{j-1}{s_i}, \frac{j}{s_i})$를 차지하고 있었다면 이동 후에는 $[\frac{j}{s_i}, \frac{j+1}{s_i})$를 차지한다. 다만 이동한 구간이 다른 생산 프로세스의 구간과 겹치면 그 프로세스는 움직이지 않는다. 슬롯을 통과하여 $[0,1)$ 밖으로 나간 프로세스는 완료된 것이며 더 이상 공간을 차지하지 않는다.
• 로하는 아직 할당하지 않은 생산 프로세스 중 하나를 골라 슬롯에 할당할 수 있고, 할당하지 않을 수도 있다. $i$번째 생산 프로세스를 할당하면 슬롯의 $[0,\frac{1}{s_i})$ 부분에 놓인다. 다만 이 구간이 다른 생산 프로세스가 차지한 구간과 겹치면 할당할 수 없다.

모든 자동차가 작업 슬롯을 거쳐 생산될 때까지 걸리는 최소 시간이 몇 초인지 구하여라.

첫 번째 줄에 생산해야 하는 자동차의 수 $N$이 주어진다. ($1 \le N \le 200,000$)

두 번째 줄에 $N$대 자동차의 생산 단계 수 $s_1, s_2, \ldots, s_N$이 공백으로 구분되어 주어진다. ($1 \le s_i \le 200,000$)

모든 자동차가 작업 슬롯을 거쳐 끝날 때까지 걸리는 최소 시간을 초 단위로 출력한다.

반열린 구간 $[a, b)$는 $a$ 이상 $b$ 미만인 모든 수를 포함한다.