#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll a[500005];
ll dp[500005][50];
int main()
{
ll i,j,k,n,m,t,s,l;
scanf("%I64d",&n);
for(i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
dp[i][0]=a[i];
}
ll dep=log2(n)+1;
for(i=0;i<n;i++)
{
for(j=1;j<=dep;j++)
{
if(i+(1<<j)-1<n)
{
dp[i][j]=__gcd(dp[i][j-1],dp[i+(1<<j)-1][j-1]);
}
}
}
set<ll>st;
for(i=0;i<n;i++)
{
ll cur=a[i];
if(cur==1)
{
st.insert(1);
continue;
}
ll s=i;
while(1)
{
ll lo=s,hi=n-1,ans=-1,gc=-1;
while(lo<=hi)
{
ll mi=(lo+hi)/2;
ll len=log2(mi-i+1);
ll cal=__gcd(dp[s][len],dp[mi-(1<<len)+1][len]);
if(cal<cur)
{
gc=cal;
hi=mi-1;
}
else ans=mi,lo=mi+1;
}
st.insert(cur);
s=ans+1;
if(s==n) break;
cur=gc;
if(cur==1)
{
st.insert(cur);
break;
}
}
}
printf("%d",st.size());
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nIGludApsbCBhWzUwMDAwNV07CmxsIGRwWzUwMDAwNV1bNTBdOwppbnQgbWFpbigpCnsKICAgIGxsIGksaixrLG4sbSx0LHMsbDsKICAgIHNjYW5mKCIlSTY0ZCIsJm4pOwogICAgZm9yKGk9MDtpPG47aSsrKQogICAgewogICAgICAgIHNjYW5mKCIlSTY0ZCIsJmFbaV0pOwogICAgICAgIGRwW2ldWzBdPWFbaV07CiAgICB9CiAgICBsbCBkZXA9bG9nMihuKSsxOwogICAgZm9yKGk9MDtpPG47aSsrKQogICAgewogICAgICBmb3Ioaj0xO2o8PWRlcDtqKyspCiAgICAgIHsKICAgICAgICAgIGlmKGkrKDE8PGopLTE8bikKICAgICAgICAgIHsKICAgICAgICAgICAgICBkcFtpXVtqXT1fX2djZChkcFtpXVtqLTFdLGRwW2krKDE8PGopLTFdW2otMV0pOwogICAgICAgICAgfQogICAgICB9CiAgICB9CiAgICBzZXQ8bGw+c3Q7CiAgICBmb3IoaT0wO2k8bjtpKyspCiAgICB7CiAgICAgICBsbCBjdXI9YVtpXTsKICAgICAgIGlmKGN1cj09MSkKICAgICAgIHsKICAgICAgICAgICBzdC5pbnNlcnQoMSk7CiAgICAgICAgICAgY29udGludWU7CiAgICAgICB9CiAgICAgICBsbCBzPWk7CiAgICAgICB3aGlsZSgxKQogICAgICAgewogICAgICAgICAgIGxsIGxvPXMsaGk9bi0xLGFucz0tMSxnYz0tMTsKICAgICAgICAgICB3aGlsZShsbzw9aGkpCiAgICAgICAgICAgewogICAgICAgICAgICAgICBsbCBtaT0obG8raGkpLzI7CiAgICAgICAgICAgICAgIGxsIGxlbj1sb2cyKG1pLWkrMSk7CiAgICAgICAgICAgICAgIGxsIGNhbD1fX2djZChkcFtzXVtsZW5dLGRwW21pLSgxPDxsZW4pKzFdW2xlbl0pOwogICAgICAgICAgICAgICBpZihjYWw8Y3VyKQogICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICBnYz1jYWw7CiAgICAgICAgICAgICAgICAgICBoaT1taS0xOwogICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgIGVsc2UgYW5zPW1pLGxvPW1pKzE7CiAgICAgICAgICAgfQogICAgICAgICAgIHN0Lmluc2VydChjdXIpOwogICAgICAgICAgIHM9YW5zKzE7CiAgICAgICAgICAgaWYocz09bikgYnJlYWs7CiAgICAgICAgICAgIGN1cj1nYzsKICAgICAgICAgICAgaWYoY3VyPT0xKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzdC5pbnNlcnQoY3VyKTsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CiAgICAgICB9CiAgICB9CiAgICBwcmludGYoIiVkIixzdC5zaXplKCkpOwoKfQo=