Дана последовательность $$$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$$$.
5 2 3 4 5 6
18