import math def main(): import sys input = sys.stdin.read data = input().split() n = int(data[0]) a = list(map(int, data[1:n+1])) total = 0 current_gcds = dict() for num in a: temp = dict() # Process previous GCDs for g in current_gcds: new_g = math.gcd(g, num) if new_g in temp: temp[new_g] += current_gcds[g] else: temp[new_g] = current_gcds[g] # Add the current number as a single-element subarray if num in temp: temp[num] += 1 else: temp[num] = 1 # Update total with the count of GCD 1 if 1 in temp: total += temp[1] # Update current_gcds for the next iteration current_gcds = temp print(total) if __name__ == "__main__": main()