#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; } /*Monoid query(int a, int b){ //演算が非可換のとき a+=sz, b+=sz; Monoid retl=e, retr=e; for(;a>=1, b>>=1){ if(b&1) retr=f(seg[--b], retr); if(a&1) retl=f(retl, seg[a++]); } return f(retl, retr); }*/ 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); } const ll MAXA=1000000000000000000; const int MAXN=500000; int main() { int n; scanf("%d", &n); assert(1<=n && n<=MAXN); vector a(n); for(int i=0; i seg(n, [&](ll x, ll y){ return gcd(x, y);}, 0, a); ll ans=0; int r=1; for(int i=0; i