Pipelined

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

• 먼저 할당된 생산 프로세스부터, 작업 슬롯의 모든 생산 프로세스들은 자신의 크기만큼 뒤로 움직인다. 즉, 작업 슬롯의 전체 구간을 $\left[ 0,1 \right)$로 표현했을 때, $i$번째 생산 프로세스가 $\left[ \frac{j-1}{s_i} ,\frac{j}{s_i} \right)$의 구간을 차지하고 있었다면, 이동 후 $\left[ \frac{j}{s_i} ,\frac{j+1}{s_i} \right)$의 구간을 차지하게 된다. 단, 이동 시 다른 생산 프로세스가 차지하는 구간과 겹치게 되는 경우에는 움직이지 않는다. 슬롯을 통과하여 $[0,1)$ 밖으로 나온 경우 이 생산 프로세스는 완료된 것이며, 더 이상 공간을 차지하지 않는다.
• 로하는 아직 할당하지 않은 생산 프로세스 중 하나를 골라 슬롯에 할당하거나 할당하지 않을 수 있다. $i$번째 생산 프로세스를 할당할 경우 슬롯의 $\left[ 0,\frac{1}{s_i} \right)$ 부분에 생산 프로세스를 할당한다. 단, 다른 생산 프로세스가 차지하고 있는 구간과 겹치는 경우 할당할 수 없다.

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

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

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

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

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