ll n,r,f,b,z,a[6d5];{rd(n,a(n));rep(l,n){while(r<=n&&gcd(f-l?a[l]:0,b)-1)b=gcd(b,a[r++]);z-=r+~n;if(f==l){b=0;rrep(i,l,f=r)a[i]=b=gcd(b,a[i]);b=0;}}wt(z);}