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: curr_gcds = [] # Process previous GCDs for g, cnt in prev_gcds: new_g = math.gcd(g, num) if curr_gcds and curr_gcds[-1][0] == new_g: curr_gcds[-1] = (new_g, curr_gcds[-1][1] + cnt) else: curr_gcds.append((new_g, cnt)) # Add the current number as a new subarray new_g = num if curr_gcds and curr_gcds[-1][0] == new_g: curr_gcds[-1] = (new_g, curr_gcds[-1][1] + 1) else: curr_gcds.append((new_g, 1)) # Update total with counts of GCD 1 for g, cnt in curr_gcds: if g == 1: total += cnt # Prepare for next iteration prev_gcds = curr_gcds print(total) if __name__ == "__main__": main()