Pipelined

Roha works at Hyundai Motor and wants to plan the production of $N$ cars using a single work slot. Producing the $i$-th car requires $s_i$ production stages. The work slot is the interval $[0,1)$ on the number line. While the $i$-th car is in production, it occupies a half-open interval of length $\frac{1}{s_i}$ in the slot. Starting at time 0, the following happens in order every second.

• First, every assigned production process moves backward by its own length. If the $i$-th process occupies $[\frac{j-1}{s_i}, \frac{j}{s_i})$, after the move it occupies $[\frac{j}{s_i}, \frac{j+1}{s_i})$. A process does not move if the move would overlap the interval of another process. A process that moves out of $[0,1)$ is complete and no longer occupies any space.
• Roha may pick one of the unassigned production processes and assign it to the slot, or may assign none. Assigning the $i$-th process places it on $[0,\frac{1}{s_i})$. It cannot be assigned if that interval overlaps an interval held by another process.

Find the minimum number of seconds until all cars have passed through the work slot.

The first line contains $N$, the number of cars to produce. ($1 \le N \le 200,000$)

The second line contains the stage counts $s_1, s_2, \ldots, s_N$ of the $N$ cars, separated by spaces. ($1 \le s_i \le 200,000$)

Print the minimum number of seconds until all cars have finished passing through the work slot.

A half-open interval $[a, b)$ contains every number greater than or equal to $a$ and less than $b$.