import sys from math import gcd def main(): n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) total = 0 prev_gcd = {} for num in a: curr_gcd = {} # Process previous GCDs for g, cnt in prev_gcd.items(): new_g = gcd(g, num) if new_g in curr_gcd: curr_gcd[new_g] += cnt else: curr_gcd[new_g] = cnt # Add the current number as a single-element subarray if num in curr_gcd: curr_gcd[num] += 1 else: curr_gcd[num] = 1 # Update the total with the count of GCD 1 total += curr_gcd.get(1, 0) # Update prev_gcd for next iteration prev_gcd = curr_gcd print(total) if __name__ == "__main__": main()