import sys import math def main(): input = sys.stdin.read().split() n = int(input[0]) a = list(map(int, input[1:n+1])) ans = 0 prev = {} # Maps GCD value to its count for subarrays ending at previous position for num in a: current = {} # Handle the subarray consisting of only the current element current_gcd = num current[current_gcd] = 1 # Merge with previous GCDs for g, cnt in prev.items(): new_gcd = math.gcd(g, num) if new_gcd in current: current[new_gcd] += cnt else: current[new_gcd] = cnt # Update the answer ans += current.get(1, 0) # Set current as prev for next iteration prev = current print(ans) if __name__ == "__main__": main()