import sys import math def main(): n = int(sys.stdin.readline()) A = list(map(int, sys.stdin.readline().split())) result = 0 last_gcds = dict() for a in A: current_gcds = dict() # 单独成一个子序列 current_gcds[a] = 1 # 处理上一步的gcd for g in last_gcds: new_gcd = math.gcd(g, a) if new_gcd in current_gcds: current_gcds[new_gcd] += last_gcds[g] else: current_gcds[new_gcd] = last_gcds[g] # 统计结果 if 1 in current_gcds: result += current_gcds[1] # 更新last_gcds last_gcds = current_gcds print(result) if __name__ == "__main__": main()