#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b struct SWAG{ using F=function; const F f; const Monoid gen; stack> fr,ba; SWAG(const F f,const Monoid &gen):f(f),gen(gen){} Monoid get(){ ll a=fr.empty()?gen:fr.top().second; ll b=ba.empty()?gen:ba.top().second; return f(a,b); } void push(Monoid x){ if(ba.empty()) ba.push(make_pair(x,x)); else ba.push(make_pair(x,f(ba.top().second,x))); } void pop(){ if(empty()) return ; if(!fr.empty()) fr.pop(); else{ while(!ba.empty()){ pair p=ba.top();ba.pop(); if(fr.empty()) fr.push(make_pair(p.first,p.first)); else fr.push(make_pair(p.first,f(p.first,fr.top().second))); } fr.pop(); } } size_t size(){ return fr.size()+ba.size(); } bool empty(){ return size()==0; } }; signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n;cin>>n; vector a(n); rep(i,n){ cin>>a[i]; } function g=[](ll a,ll b){return gcd(a,b);}; SWAG que(g,0); ll r=0,res=0; for(ll l=0;l