Если сложить...

문제

Дана последовательность $a_{i}a\_i$, состоящая из $nn$ целых положительных чисел, больших единицы. Требуется построить такую последовательность из $nn$ положительных рациональных чисел $b_{i}b\_i$, что сумма $S={\sum }_{i=1}^n{a}_i^{b_i}S=\backslash sum\backslash limits\_\{i=1\}^n\; a\_i^\{b\_i\}$ является наименьшим возможным целым числом.

입력

Первая строка входных данных содержит целое число $nn$ ($1\le n\le {10}^{4}1\; \backslash le\; n\; \backslash le\; 10^4$). Вторая строка входных данных содержит $nn$ целых чисел $a_{i}a\_i$ ($2\le a_i\le {10}^{9}2\; \backslash le\; a\_i\; \backslash le\; 10^9$).

출력

Выведите одно целое число --- наименьшее возможное целое значение $SS$.