#include using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair pii; typedef pair pll; typedef pair pdd; const ll mod = 1e9 + 7; //const ll mod = 998244353; #define REP(i,n) for(int i=0;i<(int)n;++i) //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; template bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template ostream& operator << (ostream& os, const pair v){ os << "(" << v.first << ", " << v.second << ")"; return os; } template ostream& operator << (ostream& os, const vector v){ for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os; } template ostream& operator << (ostream& os, const vector> v){ for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os; } string num2bit(ll num, ll len){ string bit = ""; REP(i, len){ bit += char('0'+(num>>i & 1)); } return bit; } template< typename Monoid > struct SegmentTree { using F = function< Monoid(Monoid, Monoid) >; int sz; vector< Monoid > seg; const F f; const Monoid M1; // n: 要素数,F: モノイド間の演算,M1: 演算の単位元 // F は無名関数で渡す SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } // k番目の要素にxを代入 void set(int k, const Monoid &x) { seg[k + sz] = x; } // 構築 void build() { for(int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } // k番目の値をxに変更 void update(int k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } // 区間[a, b)に関して演算して結果を返す Monoid query(int a, int b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } // k番目の値を返す(set[k]でアクセス) Monoid operator[](const int &k) const { return seg[k + sz]; } template< typename C > int find_subtree(int a, const C &check, Monoid &M, bool type) { while(a < sz) { Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]); if(check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template< typename C > //[a, x)がcheckを満たす最初の要素位置xを返す int find_first(int a, const C &check) { Monoid L = M1; if(a <= 0) { if(check(f(L, seg[1]))) return find_subtree(1, check, L, false); return -1; } int b = sz; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) { Monoid nxt = f(L, seg[a]); if(check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } //[x, b)がcheckを満たす最後の要素位置xを返す template< typename C > int find_last(int b, const C &check) { Monoid R = M1; if(b >= sz) { if(check(f(seg[1], R))) return find_subtree(1, check, R, true); return -1; } int a = sz; for(b += sz; a < b; a >>= 1, b >>= 1) { if(b & 1) { Monoid nxt = f(seg[--b], R); if(check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; vector A(N); REP(i, N) cin >> A[i]; SegmentTree seg(N, [](ll a, ll b){return gcd(a, b);}, 0); REP(i, N) seg.set(i, A[i]); seg.build(); ll res = 0; REP(i, N){ ll ng = i-1; ll ok = N; while(ok-ng>1){ ll md = (ng+ok)/2; ll tmp = seg.query(i, md+1); if(tmp==1) ok = md; else ng = md; } //dump(ok) res += (N-ok); } cout << res << endl; return 0; }