# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

Arrayman is a very famous person. He has an array of n integers. He wants to divide it in a number of subarrays. The cost to create a subarray is the sum of the unique numbers in that subarray. He has to spend sum of unique numbers in each subarray for this. For example: If the array is **(2,4,4,6)** and he decides to divide like this: **{2}, {4,4,6}** then total cost will be **2+4+6=12** Taka. But if he divides like this: **{2,4},{4,6}** then total cost will be **2+4+4+6=16** Taka. Arrayman can divide the array in any number of possible subarrays he wishes (he also can leave the array as it is). But he has to follow one condition. **GCD of each subarray must be greater than 1**. For example **{2,4,6}** can be a subarray. But he can’t take **{2,4,3}** as it’s gcd is 1. In this problem, you need to find the minimum amount of money Arrayman has to spend.

Input starts with integer **n** (**1<=n<=10^5**). Next line contains n space separated integers . i^{th} of them contains **a1, a2, …, an** **(2<=ai<=10^6)**

Print n lines. i^{th} line contains an integer denoting the answer if we consider first i elements of the array

Input | Output |
---|---|

4 2 3 3 4 | 2 5 5 9 |

Input | Output |
---|---|

4 2 3 4 5 | 2 5 9 14 |

0% Solution Ratio

Login to submit

Topics : Seive, dynamic Programming, segment tree. First, we need to find a naive solution. Then we...