G. Gorgeous Summation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a sequence $$$b$$$ consisting of an even number of positive integers, let us call an integer $$$x$$$ its radius if there exists an integer $$$i$$$ such that the sum of the $$$i$$$-th leftmost and the $$$i$$$-th rightmost elements of $$$b$$$ is equal to $$$x$$$. For example, the sequence $$$(16, 11, 20, 24)$$$ has two distinct radii: $$$31$$$ and $$$40$$$.

Define the gorgeousness of a sequence of even length as the greatest common divisor of all its radii. For example, for the sequence above, it is equal to $$$1$$$.

A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deleting several (possibly zero or all) elements from the beginning and several (possibly zero or all) elements from the end.

You are given a sequence $$$a$$$ of $$$n$$$ integers. Find the sum of the gorgeousness values over all its nonempty subsegments of even length.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 100\,000$$$): the length of the sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$): the elements of the sequence.

Output

Print a single integer: the desired sum.

Example
Input
5
1 2 3 4 5
Output
36
Note

In the example test case, there are four subsegments of length $$$2$$$. They have gorgeousness values of $$$3$$$, $$$5$$$, $$$7$$$, and $$$9$$$, from left to right.

There are two subsegments of length $$$4$$$ (containing all the elements except $$$1$$$ or $$$5$$$). The subsegment containing $$$1$$$ has a gorgeousness of $$$5$$$, while the subsegment containing $$$5$$$ has a gorgeousness of $$$7$$$.

Therefore, the answer is $$$(3+5+7+9)+(5+7) = 36$$$.