Dynamic Programming Optimization with Convex Hull Trick
There are N boxes. The ith box contains ai candies. The frog Om Nom is sitting in box number 1. Om Nom wants to collect as many candies as he can. However, Om Nom jumps in a peculiar fashion. Om Nom can jump from box number j to box number i only if j divides i. Whenever Om Nom lands in a box, he collects all the candies in that box. You have to report the maximum number of Candies that Om Nom can collect for all i from 1 to N if i is the last box that Om Nom visits.See the samples for more details.
Constraints
0<=ai<=100000
1<=N<=100000
Input
The first line contains the number N.
The second line contains the array a , the ith integer denoting the number of candies in the ith box.
Output
Print N integers-the ith integer should be the maximum number of candies that Om Nom can collect if the ith box is his final box (i.e his sequence of jumps ends at i).
