spoj#ADAGF. Ada and Greenflies
Ada and Greenflies
As you might already know, Ada the Ladybug is a farmer. Beside of growing vegetable she also breeds greenflies. There are many kinds of greenflies and it is not trivial to breed them since they behave very strangely. Each kind of greenfly is known under a number. As you have multiple greenflies in a single coop, they produce as much juice as the greatest common divisor of their numbers.
Ada owns a row of greenflies (of several kinds) and she can split them by a fence, so that always a continuous segment of greenflies will be in a same coop
Ada wants to find out the sum of procution of greenflies over all possible continuous segments (of size at least one), can you help her?
Input
The first line contains an integer 1 ≤ N ≤ 3*105, the number of greenflies in row.
The second line contains N integers 0 ≤ ai ≤ 106
Output
Print a single line: the sum of production of all continuous segments.
Example Input
5 2 2 3 6 2
Example Output
29
Example Input 2
7 2 4 6 12 18 6 4
Example Output 2
118
Example Input 3
5 2 4 8 16 32
Example Output 3
114
Example Input 4
4 12 20 20 5
Example Output 4
96