Монокарп попал на необитаемый остров. Он решил обойти весь остров и обнаружил, что на нем есть $$$n$$$ пальм, причем на $$$i$$$-й пальме растет $$$a_i$$$ кокосов.
Монокарп решил выбрать целое положительное число $$$x$$$ и собрать все кокосы со всех пальм, количество кокосов на которых является целой положительной степенью числа $$$x$$$. Иными словами, Монокарп соберет все кокосы с $$$i$$$-й пальмы, если число $$$a_i$$$ можно представить в виде числа $$$x^{m}$$$, где $$$m$$$ — целое положительное число.
Перед вами стоит задача помочь Монокарпу и определить максимально возможное количество кокосов, которое он может собрать, выбрав какое-то число $$$x$$$.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество пальм с кокосами.
Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно количеству кокосов, которые растут на $$$i$$$-й пальме.
Выведите максимальное количество кокосов, которые может собрать Монокарп, выбрав какое-то целое положительное число $$$x$$$.
5 4 8 25 5 16
30
3 9 27 40
40
6 1 1 4 1 1 1
5
В первом примере Монокарпу нужно выбрать $$$x = 5$$$. Тогда он сможет собрать кокосы с третьей и четвертой пальм, и суммарное количество собранных кокосов будет равно $$$25 + 5 = 30$$$.
Во втором примере Монокарпу нужно выбрать $$$x = 40$$$. Тогда он сможет собрать кокосы с третьей пальмы, то есть количество собранных кокосов будет равно $$$40$$$. Если бы Монокарп выбрал число $$$3$$$, то смог бы собрать кокосы с первой и второй пальм. Количество кокосов на этих пальмах равно $$$9 + 27 = 36$$$, но это количество меньше, что для $$$x = 40$$$.
В третьем примере Монокарпу нужно выбрать $$$x = 1$$$. Тогда он сможет собрать $$$5$$$ кокосов со всех пальм, кроме третьей.
