410388: GYM104015 F Coconuts

Monocarp is stranded on a deserted island! After exploring the island, he found out that $$$n$$$ palms grow on it, and there are $$$a_i$$$ coconuts on the $$$i$$$-th palm.

Monocarp has decided to choose a positive integer $$$x$$$ and gather coconuts from each palm such that the number of coconuts on that palm is an integer positive power $$$x$$$. In other words, Monocarp will gather all of the coconuts from the $$$i$$$-th palm, if $$$a_i$$$ can be represented as $$$x^{m}$$$, where $$$m$$$ is a positive integer.

Your task is to help Monocarp choose $$$x$$$ optimally and gather the maximum possible number of coconuts.

The first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of palms.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the number of coconuts growing on the $$$i$$$-th palm.

Print one integer — the maximum number of coconuts Monocarp can gather if he chooses $$$x$$$ optimally.

5
4 8 25 5 16

30

3
9 27 40

40

6
1 1 4 1 1 1

5

In the first example, Monocarp should choose $$$x = 5$$$. Then he can gather the coconuts from the third palm and the fourth palm, getting $$$25 + 5 = 30$$$ coconuts in total.

In the second example, Monocarp should choose $$$x = 40$$$. Then he can gather $$$40$$$ coconuts from the third palm. If Monocarp chooses, for example, $$$3$$$, he can gather the coconuts from the first two palms, but then he will get only $$$9 + 27 = 36$$$ coconuts which is less than the result for $$$x = 40$$$.

In the third example, Monocarp should choose $$$x = 1$$$. Then he can gather $$$5$$$ coconuts.