24628번 - Если сложить... 다국어

Дана последовательность $a_i$, состоящая из $n$ целых положительных чисел, больших единицы. Требуется построить такую последовательность из $n$ положительных рациональных чисел $b_i$, что сумма $S=\sum\limits_{i=1}^n a_i^{b_i}$ является наименьшим возможным целым числом.

Первая строка входных данных содержит целое число $n$ ($1 \le n \le 10^4$). Вторая строка входных данных содержит $n$ целых чисел $a_i$ ($2 \le a_i \le 10^9$).

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