#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; template struct SegmentTree{ using F=function; int sz; vector seg; const F f; const Monoid e; SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){ sz=1; while(sz v): f(f), e(e){ sz=1; while(sz=1; i--){ seg[i]=f(seg[2*i], seg[2*i+1]); } } void update(int k, const Monoid &x){ k+=sz; seg[k]=x; while(k>1){ k>>=1; seg[k]=f(seg[2*k], seg[2*k+1]); } } Monoid query(int a, int b){ a+=sz, b+=sz; Monoid ret=e; for(;a>=1, b>>=1){ if(b&1) ret=f(ret, seg[--b]); if(a&1) ret=f(ret, seg[a++]); } return ret; } template int binarysearch(int st, C &check, Monoid &s, int k, int l, int r){ if(k>=sz){ s=f(s, seg[k]); if(check(s)) return k-sz; else return -1; } int m=(l+r)>>1; if(m<=st) return binarysearch(st, check, s, 2*k+1, m, r); if(st<=l && !check(f(s, seg[k]))){ s=f(s, seg[k]); return -1; } int vl=binarysearch(st, check, s, 2*k, l, m); if(vl!=-1) return vl; return binarysearch(st, check, s, 2*k+1, m, r); } template int binarysearch(int st, C &check){ Monoid s=e; return binarysearch(st, check, s, 1, 0, sz); } Monoid operator[](const int &k) const{ return seg[k+sz]; } }; ll gcd(ll a, ll b){ if(b==0) return a; return gcd(b, a%b); } int main() { int n; scanf("%d", &n); vector a(n); for(int i=0; i seg(n, [&](ll x, ll y){ return gcd(x, y);}, 0, a); ll ans=0; for(int i=0; i