#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long gcd(long a,long b){return b?gcd(b,a%b):a;}
vector<pair<long,long> >had,til;
void psh(long X)
{
	if(til.empty())
	{
		til.push_back(make_pair(X,X));
		return;
	}
	long pre=til.back().first;
	til.push_back(make_pair(gcd(pre,X),X));
}
void pp()
{
	if(had.empty())
	{
		had=til;
		reverse(had.begin(),had.end());
		til.clear();
		long cum=0;
		for(int i=0;i<had.size();i++)
		{
			cum=gcd(cum,had[i].second);
			had[i].first=cum;
		}
	}
	had.pop_back();
}
long query()
{
	long L=had.empty()?0L:had.back().first;
	long R=til.empty()?0L:til.back().first;
	return gcd(L,R);
}
long N;
main()
{
	cin>>N;
	long ans=N*(N+1)/2;
	for(int i=0;i<N;i++)
	{
		long A;cin>>A;psh(A);
		while(query()==1)pp();
		ans-=had.size()+til.size();
	}
	cout<<ans<<endl;
}