import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
N = int(readline())
A = np.array(read().split() + [1], np.int64)

# sparse table
sp = [np.ones(N + 1, np.int64) for _ in range(20)]
sp[0] = A
for n in range(1, 20):
    dx = 1 << (n - 1)
    sp[n][:-dx] = np.gcd(sp[n - 1][:-dx], sp[n - 1][dx:])

# [L,R) の gcd は 1 ではない。のうちで R を 最大化
L = np.arange(N)
R = L.copy()
G = np.zeros(N, np.int64)
for n in range(19, -1, -1):
    G1 = np.gcd(G, sp[n][R])
    go = G1 != 1
    R[go] += 1 << n
    G[go] = G1[go]

ng = (R - L).sum()
total = N * (N + 1) // 2
print(total - ng)