Parallel Universe

In the year 2XXX, Earth is on the verge of colliding with an asteroid. The brilliant scientist Kipa is given the heavy task of roaming the parallel universe to find a planet that can replace Earth.

We are currently on Earth (= planet 0). After weighing many factors, we have found that it is optimal in cost to visit planet 1, planet 2, …, planet (n-1) in that order and return to Earth (= planet n). For every integer 1 ≤ i < n, planet i is not Earth.

Earth has a special device called the "ultra-high-speed walking machine" that can raise the speed as much as desired. Once you leave Earth, you can only lower the speed, never raise it.

In principle, you must match exactly the speed required to go to the next region, but fortunately the parallel universe is spaced at regular intervals, so you can also move to the next region at a positive integer multiple of the required speed. Also, since you are moving fast enough and you can tell right after arriving whether a planet is suitable as a replacement for Earth, you may at some planet keep your speed after arriving and move on to the next planet.

For every 1 ≤ i ≤ n, the (minimum) speed vi required to move from planet (i-1) to planet i is given. Minimize the speed you must raise on Earth.

The first line gives n (1 ≤ n ≤ 3·105).

The second line gives n integers v1, v2, …, vn, separated by spaces. For every integer 1 ≤ i ≤ n, 1 ≤ vi ≤ 109 holds.

Print one number. This number is the minimum speed you must raise on Earth.

If you travel at three times the speed needed to reach planet 1, and at twice the speed for planet 2, you only need to build up a speed of 900 on Earth.