import sys input = sys.stdin.readline from math import gcd n = int(input()) a = list(map(int,input().split())) table = [[0 for i in range(n)] for j in range(20)] def judge(ls): l = len(ls) ret = 0 stack1 = [ls[l//2-1]] stack2 = [ls[l//2]] for i in range(l//2): if l//2-i-2 >= 0: stack1.append(gcd(ls[l//2-i-2],stack1[-1])) if i+l//2+1 <= l-1: stack2.append(gcd(ls[i+l//2+1],stack2[-1])) s1l = len(stack1) s2l = len(stack2) lf = s1l-1 r = 0 for r in range(s2l): while lf >= 0 and gcd(stack1[lf],stack2[r]) == 1: ret += s2l-r if lf > 0: lf -= 1 else: break if gcd(stack1[lf],stack2[r]) == 1: break return ret for i in range(20): if i == 0: for j in range(n): if a[j] == 1: table[i][j] = 1 else: table[i][j] = 0 continue for j in range(n): if j*2**i >= n: if j == 1: print(table[i][0]) exit() else: break table[i][j] = table[i-1][j//2]+table[i-1][j//2+1]+judge(a[j*2**i:(j+1)*2**i])