You have to travel to different villages to make some profit.
In each village, you gain some profit. But the catch is, from a particular village i, you can only move to a village j if and only if \(i < j\) and the profit gain from village j is a multiple of the profit gain from village i.

You have to tell the maximum profit you can gain while traveling.

Input format

The first line contains a single integer N denoting the total number of villages.
The second line contains N space-separated integers, each denoting the profit gain \(P_i\) from village i.

Output format

Print the maximum profit you can gain.

Constraints

\(1 \le N \le 10^3\)
\(0 \le P_i \le 10^5\)