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

시간 제한1초메모리 제한512 MB

요약

1보다 큰 정수 a_i가 주어질 때, a_i^b_i들의 합이 정수가 되면서 가장 작아지도록 양의 유리수 지수 b_i를 정하고 그 최솟값을 출력한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

Дана последовательность $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$ .

예제1

예제 1
입력
```
5
2 3 4 5 6
```
예상 출력
```
18
```