import sys import math def main(): n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) ans = 0 prev_gcds = {} for num in a: current_gcds = {} # 将当前元素单独作为一个子序列 current_gcds[num] = 1 # 遍历前一个位置的所有可能的gcd值 for g in prev_gcds: new_gcd = math.gcd(g, num) if new_gcd in current_gcds: current_gcds[new_gcd] += prev_gcds[g] else: current_gcds[new_gcd] = prev_gcds[g] # 统计当前字典中gcd为1的数量 ans += current_gcds.get(1, 0) # 更新prev_gcds为当前的字典 prev_gcds = current_gcds print(ans) if __name__ == "__main__": main()