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){rrep(i,l,r-1)a[i]=gcd(((a+i))(2));f=r;b=0;}}wt(z);}