Clockwork Archives

Deep beneath the city lies the Clockwork Archive, a vault containing ancient mechanical records. Each record is operated by a gear that completes one revolution after a fixed number of ticks.

An archivist may activate exactly three records at a time. However, the gear with the longest revolution cycle is too slow to affect the experiment and is automatically disconnected.

The remaining two gears begin at their starting positions simultaneously. The archivist records how often their starting positions coincide: this value is equal to the greatest number of equal-length phases into which both revolution cycles can be divided.

For example, gears with cycles of $12$ and $18$ ticks can both be divided into $6$ equal phases, so their compatibility value is $6$.

Formally, for three cycle lengths $x$, $y$, and $z$:

1. Arrange them so that $x \le y \le z$.
2. Disconnect the gear with cycle length $z$.
3. The experiment produces a compatibility value of \[\gcd(x,y).\]

You are given $N$ records in their shelf order. For every choice of three different records with positions $1 \le i < j < k \le n$, perform the experiment using the cycle lengths $a_i$, $a_j$, and $a_k$. Find the sum of the compatibility values produced by all experiments.

The first line contains an integer $N$ ($3 \le N \le 200\,000$), the number of records.

The second line contains $N$ integers $a_1,a_2,\cdots,a_n$, where $a_i$ is the revolution cycle of the $i$-th record. ($1 \le a_i \le 10^{6}$)

Print one integer: the total compatibility value of all experiments.