A. Number Game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Robi and Aritro are good friends and math enthusiasts who frequently debate over who has the ultimate mathematical rizz and aura. To settle the debate and prove that he is the absolute goat, Aritro challenges Robi with a problem that targets his weakness in numbers. If Robi loses, Aritro pulls all the huzz; if Robi wins, his rizz is unmatched.

Aritro gives him an array $$$a$$$ of $$$n$$$ distinct integers greater than 1. Using normal numbers is lowkey mid for Aritro. Instead, he uses prime powers! Each element $$$a_i$$$ is a prime power, meaning that $$$a_i = p^q$$$ for some prime $$$p$$$ and integer $$$q \ge 1$$$.

Aritro challenges Robi to choose $$$k$$$ indices, where $$$1 \le k \le n$$$, satisfying $$$i_1 \lt i_2 \lt \dots \lt i_k$$$ such that the corresponding array values form a strictly increasing subsequence. More formally, the chosen elements must satisfy:

$$$$$$a_{i_1} \lt a_{i_2} \lt \dots \lt a_{i_k}$$$$$$

Let $$$f(a_i) = q$$$ denote the exponent of $$$a_i$$$. Robi must choose a subsequence whose total exponent sum is as large as possible. More formally, output:

$$$$$$\sum_{j=1}^{k} f(a_{i_j})$$$$$$

Output the maximum possible value of this sum.

Constraints

  • $$$1 \le n \le 10^5$$$
  • $$$1 \le q \le 59$$$
  • All elements in the array $$$a$$$ are unique.
Input
  • Line 1: A single integer $$$n$$$ representing the size of the array.
  • Line 2: $$$n$$$ space-separated integers representing the elements of array $$$a$$$.
Output
  • Line 1: Output a single integer representing the maximum possible sum of the exponents.
Scoring

Subtasks

SubtaskPointsAdd. constraints
$$$1$$$$$$5$$$$$$n = 1$$$, $$$a[i] \le 10^6$$$
$$$2$$$$$$8$$$$$$n \le 16$$$, $$$q = 1$$$
$$$3$$$$$$7$$$$$$n \le 16$$$, $$$a[i] \le 10^6$$$
$$$4$$$$$$15$$$$$$n = 1$$$
$$$5$$$$$$10$$$$$$ n \le 16$$$
$$$6$$$$$$15$$$$$$q=1$$$
$$$7$$$$$$40$$$No additional constraints
Example
Input
4
16 27 3 2
Output
7
Note

In the first example, the prime power representations of the elements are:

  • $$$a_1 = 16 = 2^4$$$ $$$\Rightarrow$$$ $$$f(16) = 4$$$.
  • $$$a_2 = 27 = 3^3$$$ $$$\Rightarrow$$$ $$$f(27) = 3$$$.
  • $$$a_3 = 3 = 3^1$$$ $$$\Rightarrow $$$ $$$f(3) = 1 $$$.
  • $$$a_4 = 2 = 2^1$$$ $$$\Rightarrow$$$ $$$f(2) = 1$$$.

The optimal strictly increasing subsequence is $$$[16, 27]$$$, obtained by choosing $$$i_1 = 1$$$ and $$$i_2 = 2$$$. The maximum possible sum of the exponents is $$$f(16) + f(27) = 4 + 3 = 7$$$.