#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(void) {
	int n;
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];

	int lg = 20;
	vector<vector<ll>> table(lg, vector<ll>(n));
	for(int i = 0; i < n; i++) table[0][i] = a[i];

	// cerr << 1 << endl;

	for(int j = 0; j+1 < lg; j++) {
		for(int i = 0; i+(1<<(j+1)) <= n; i++) {
			table[j+1][i] = gcd(table[j][i], table[j][i+(1<<j)]);
		}
	}

	// cerr << 2 << endl;

	// prod gcd[l, r)
	auto prod = [&](int l, int r) {
		int k = 63 - __builtin_clzll((ll)(r-l));
		return gcd(table[k][l], table[k][r-(1<<k)]);
	};

	int ans = 0;

	int r = 0;
	for(int l = 0; l < n; l++) {
		if(r < l) r = l;

		// cerr << r << " " << l << endl;
		while(r < n && prod(l, r+1) != 1) {
			r++;
		}

		ans += r-l;
	}

	//cout << ans << endl;
	cout << n*(n+1)/2 - ans << endl;
}