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*10⁵, the number of greenflies in row.

The second line contains N integers 0 ≤ a_i ≤ 10⁶

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