#include #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define ALL(v) (v).begin(), (v).end() #define LLA(v) (v).rbegin(), (v).rend() #define PB push_back #define MP(a, b) make_pair((a), (b)) using namespace std; template inline vector make_vec(size_t a, T val) { return vector(a, val); } template inline auto make_vec(size_t a, Ts... ts) { return vector(a, make_vec(ts...)); } template inline T read() { T t; cin >> t; return t; } template inline vector readv(size_t sz) { vector ret(sz); rep(i, sz) cin >> ret[i]; return ret; } template inline tuple reads() { return {read()...}; } template struct edge { int to; T cost; edge(int t, T c) : to(t), cost(c) {} }; using ll = long long; using pii = pair; using pll = pair; using Graph = vector>; template using WGraph = vector>>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; /* SegmentTree(0-indexed) */ template struct SegmentTree { using F = function; const F f; const Monoid e; int n; vector dat; SegmentTree(int _n, const F _f, const Monoid &_e) : f(_f), e(_e) { n = 1; while(n < _n) n *= 2; dat.assign(2 * n, e); } SegmentTree(vector v, const F _f, const Monoid &_e) : f(_f), e(_e) { int sz = v.size(); n = 1; while(n < sz) n *= 2; dat.resize(2 * n); for(int i = 0; i < sz; i++) set(i, v[i]); build(); } void set(int k, Monoid a) { dat[k + n] = a; } void build() { for(int i = n - 1; i > 0; i--) { dat[i] = f(dat[2 * i], dat[2 * i + 1]); } } void update(int k, const Monoid &a) { k += n; dat[k] += a; while(k >>= 1) { dat[k] = f(dat[k * 2], dat[k * 2 + 1]); } } Monoid at(int a) { return query(a, a + 1); } // query for [a,b) Monoid query(int a, int b) { Monoid vl = e, vr = e; a += n, b += n; for(; a < b; a >>= 1, b >>= 1) { if(a & 1) vl = f(vl, dat[a++]); if(b & 1) vr = f(dat[--b], vr); } return f(vl, vr); } }; template struct RgcdQ : SegmentTree { using Segtree = SegmentTree; static auto f(T a, T b) { return __gcd(a, b); } RgcdQ(ll n, const T &e = 0) : Segtree(n, f, e) {} RgcdQ(const vector &A, const T &e = 0) : Segtree(A, f, e) {} }; ll f(ll a, ll b) { return __gcd(a, b); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N = read(); auto A = readv(N); RgcdQ seg(A); ll res = 0; int right = 0; for(int left = 0; left < N; left++) { while(right < N && seg.query(left, right + 1) != 1) right++; res += N - right; } cout << res << endl; }