#define PROBLEM "https://yukicoder.me/problems/4072" #include using namespace std; #define call_from_test #ifndef call_from_test #include using namespace std; #endif //BEGIN CUT HERE template struct DisjointSparseTable{ using F = function; vector< vector > dat; vector ht; const F f; DisjointSparseTable(){} DisjointSparseTable(F f):f(f){} void build(const vector &vs){ int n=vs.size(),h=1; while((1<(n)); ht.assign((1<>1]+1; for(int j=0;j=j;k--) dat[i][k]=f(vs[k],dat[i][k+1]); if(n<=t) break; dat[i][t]=vs[t]; int r=min(t+s,n); for(int k=t+1;k=--r) return dat[0][l]; return f(dat[ht[l^r]][l],dat[ht[l^r]][r]); } }; //END CUT HERE #ifndef call_from_test // find with non-idempotent monoid signed CODECHEF_SEGPROD(){ int T; scanf("%d",&T); int p; auto f=[&](int a,int b)->int{return (long long)a*b%p;}; DisjointSparseTable dst(f); for(int t=1;t<=T;t++){ int n,q; scanf("%d %d %d",&n,&p,&q); vector v(n); for(int i=0;i b(q/64+2); for(int i=0;i<(q/64+2);i++) scanf("%d",&b[i]); dst.build(v); int x=0,l=0,r=0; for(int i=0;ir) swap(l,r); x=dst.query(l,r+1)+1; if(x>=p) x-=p; } printf("%d\n",x); } return 0; } /* verified on 2019/10/29 https://www.codechef.com/problems/SEGPROD */ //INSERT ABOVE HERE signed main(){ //CODECHEF_SEGPROD(); return 0; } #endif #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; int n; cin>>n; vector as(n); for(int i=0;i>as[i]; auto f=[&](ll a,ll b){return gcd(a,b);}; DisjointSparseTable dst(f); dst.build(as); return 0; ll ans=0; for(int i=0;i>1; if(dst.query(i,m)==1) r=m; else l=m; } ans+=n-l; } cout<