BARMAN

Professor Bajtych studies arithmetic sequences modulo an arbitrary integer $N$. For an integer $a$, its order modulo $n$ is the smallest integer $m > 0$ such that $a \cdot m$ is divisible by $n$; equivalently, $m = n / \gcd(a, n)$.

Bajtych secretly fixes a sequence of $k$ integers $a_1, a_2, \dots, a_k$ together with a modulus $n$, but reveals to you only the order $m_i$ of each $a_i$ modulo $n$. You may then request a sequence of operations (at most $2k$ of them). A single operation picks a contiguous range and a constant $c$, and multiplies every element $a_l, a_{l+1}, \dots, a_r$ in that range by $c$. After all of your operations are applied, Bajtych pays you an amount, in B$, equal to the order of the sum $a_1 + a_2 + \dots + a_k$ modulo $n$.

Bajtych is greedy. He commits to the modulus $n$ and to the concrete values $a_1, \dots, a_k$ only after he has seen every operation you requested, and he always chooses them (consistent with the announced orders $m_i$) so as to pay you as little as possible.

Determine the largest payment you can guarantee for yourself, no matter how Bajtych later chooses $n$ and the values $a_i$.

The first line contains a single integer $k$ ($1 \le k \le 100$).

The second line contains $k$ integers $m_1, m_2, \dots, m_k$ ($1 \le m_i < 2^{64}$), where $m_i$ is the order of $a_i$ modulo $n$.

Print a single integer: the largest payment, in B$, that you can guarantee regardless of how Bajtych later chooses the modulus $n$ and the values $a_i$ consistent with the given orders.

This value can be extremely large (up to thousands of digits), so compute and print it in full using big-integer arithmetic.