import sys import math def main(): n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) total = 0 prev_gcds = {} for num in a: current_gcds = {} # 单独考虑当前数 current_gcds[num] = 1 # 遍历prev_gcds中的每个gcd值 for g in prev_gcds: new_g = math.gcd(g, num) if new_g in current_gcds: current_gcds[new_g] += prev_gcds[g] else: current_gcds[new_g] = prev_gcds[g] # 统计当前的gcd=1的数量 if 1 in current_gcds: total += current_gcds[1] # 更新prev_gcds为current_gcds prev_gcds = current_gcds print(total) if __name__ == "__main__": main()