#ifndef LOCAL #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx") #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using VI = vector; using VVI = vector>; using VLL = vector; using VVLL = vector>; using VB = vector; using PII = pair; using PLL = pair; template using minheap = priority_queue, greater>; const int INF = 1000000007; const ll INF_LL = 1'000'000'000'000'000'007; #define __overload3(_1, _2, _3, name,...) name #define rep(...) __overload3(__VA_ARGS__, repFromUntil, repUntil, repeat)(__VA_ARGS__) #define repeat(times) repFromUntil(_name##__LINE__, 0, times) #define repUntil(name, times) repFromUntil(name, 0, times) #define repFromUntil(name, from, until) for (int name = from, name##__until = (until); name < name##__until; name++) #define repr(...) __overload3(__VA_ARGS__, reprFromUntil, reprUntil, repeat)(__VA_ARGS__) #define reprUntil(name, times) reprFromUntil(name, 0, times) #define reprFromUntil(name, from, until) for (int name = (until) - 1, name##__from = (from); name >= name##__from; name--) #define EXIT(out) do { OUT(out); exit(0); } while (0) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #ifdef LOCAL #define debug(v) do {debugos << "L" << __LINE__ << " " << #v << " > ";debugos<<(v)< ";for(auto e:(v)){debugos< ";for(int x=0;x<(w);x++){debugos<<(m)[x]<<" ";}debugos< \n";for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){debugos<<(m)[y][x]<<" ";}debugos< bool chmin(T& var, U x) { if (var > x) { var = x; return true; } else return false; } template bool chmax(T& var, U x) { if (var < x) { var = x; return true; } else return false; } template int sgn(T val) { return (T(0) < val) - (val < T(0)); } ll power(ll e, int t, ll mod = INF_LL) { ll res = 1; while (t) { if (t&1) res = (res * e) % mod; t >>= 1; e = (e * e) % mod; } return res; } template T divceil(T m, T d) { assert(m >= 0 and d > 0); return (m+d-1)/d; } template vector make_v(size_t a, T b) { return vector(a, b); } template auto make_v(size_t a, Ts... ts) { return vector(a, make_v(ts...)); } string operator*(const string& s, int times) { string res = ""; rep(times) res += s; return res; } struct Edge { int to; ll cost; Edge(int _to): to(_to), cost(1) {} Edge(int _to, ll _cost): to(_to), cost(_cost) {} operator int() { return to; } }; using Graph = vector>; class MyScanner { public: int offset = 0; char nc(){ #ifdef LOCAL return getchar(); #else return getchar_unlocked(); #endif } template void input_integer(T& var) { var = 0; T sign = 1; int cc = nc(); for (; cc<'0' || '9'>(char& var) { var = c(); return *this; } MyScanner& operator>>(int& var) { input_integer(var); return *this; } MyScanner& operator>>(ll& var) { input_integer(var); return *this; } MyScanner& operator>>(string& var) { var = ""; int cc = nc(); for (; !isvisiblechar(cc); cc = nc()); for (; isvisiblechar(cc); cc = nc()) var.push_back(cc); return *this; } template operator T() { T x; *this >> x; return x; } template void operator()(T &t) { *this >> t; } template void operator()(T &t, Ts &...ts) { *this >> t; this->operator()(ts...); } template void iter(Iter first, Iter last) { while (first != last) *this >> *first, first++; } VI vi(int n) { VI res(n); iter(all(res)); return res; } VVI vvi(int n, int m) { VVI res(n); rep(i, n) res[i] = vi(m); return res; } VLL vll(int n) { VLL res(n); iter(all(res)); return res; } VVLL vvll(int n, int m) { VVLL res(n); rep(i, n) res[i] = vll(m); return res; } template vector v(int n) { vector res(n); iter(all(res)); return res; } private: int isvisiblechar(int c) { return 0x21 <= c && c <= 0x7E; } } IN, IN1{-1}; class MyPrinter { public: int offset = 0; template void output_integer(T var) { var += offset; if (var == 0) { putchar('0'); return; } if (var < 0) putchar('-'), var = -var; char stack[32]; int stack_p = 0; while (var) stack[stack_p++] = '0' + (var % 10), var /= 10; while (stack_p) putchar(stack[--stack_p]); } MyPrinter& operator<<(char c) { putchar(c); return *this; } MyPrinter& operator<<(double x) { printf("%.10f", x); return *this; } template MyPrinter& operator<<(T var) { output_integer(var); return *this; } MyPrinter& operator<<(char* str_p) { while (*str_p) putchar(*(str_p++)); return *this; } MyPrinter& operator<<(const char* str_p) { while (*str_p) putchar(*(str_p++)); return *this; } MyPrinter& operator<<(const string& str) { const char* p = str.c_str(); const char* l = p + str.size(); while (p < l) putchar(*p++); return *this; } template void operator()(T x) { *this << x << newl; } template void operator()(T x, Ts ...xs) { *this << x << " "; this->operator()(xs...); } template void iter(Iter s, Iter t) { if (s == t) *this << "\n"; else for (; s != t; s++) *this << *s << " \n"[next(s, 1) == t]; } template void range(const Range& r) { iter(begin(r), end(r)); } } OUT, OUT1{1}; class DebugPrint { public: template DebugPrint& operator <<(const T& v) { #ifdef LOCAL cerr << v; #endif return *this; } } debugos; template OutStream& operator<<(OutStream& out, const pair& var) { return out << var.first << " " << var.second; } template * = nullptr> OutStream& tuple_impl(OutStream& out, const Tuple& var) { return out; } template * = nullptr> OutStream& tuple_impl(OutStream& out, const Tuple& var) { out << get(var) << " "; return tuple_impl(out, var); } template OutStream& operator<<(OutStream& out, const tuple& var) { return tuple_impl, 0, sizeof...(Ts)>(out, var); } template InStream& operator>>(InStream& in, pair& var) { return in >> var.first >> var.second; } template * = nullptr> InStream& tuple_impl(InStream& in, Tuple& var) { return in; } template * = nullptr> InStream& tuple_impl(InStream& in, Tuple& var) { in >> get(var); return tuple_impl(in, var); } template InStream& operator>>(InStream& in, tuple& var) { return tuple_impl, 0, sizeof...(Ts)>(in, var); } template class Swag { private: vector L, R; vector accL, accR; const T unit; const F f; public: Swag(T _unit = T(), F _f = F()) : L(), R(), accL(), accR(), unit(_unit), f(_f) {} template Swag(Iter first, Iter last, T _unit = T(), F _f = F()) : L(make_reverse_iterator(last), make_reverse_iterator(first)), R(), accL(), accR(), unit(_unit), f(_f) { buildL(); } public: void push(T x) { R.push_back(x); accR.push_back(accR.empty() ? x : f(accR.back(), x)); } void pop() { prepareL(); L.pop_back(); } T fold() const { T res = L.empty() ? unit : accL[L.size()-1]; if (not R.empty()) res = res == unit ? accR[R.size()-1] : f(res, accR[R.size()-1]); return res; } private: void buildL() { accL.resize(L.size()); if (not accL.empty()) { accL[0] = L[0]; rep(i, 1, accL.size()) accL[i] = f(L[i], accL[i-1]); } } void prepareL() { if (L.empty()) { reverse(all(R)); swap(L, R); buildL(); accR.clear(); } } }; int main() { int n = IN; auto a = IN.vll(n); Swag)> swag(0, __gcd); ll res = 0; int r = 0; rep(l, n) { while (r <= l) swag.push(a[r++]); while (r < n and swag.fold() != 1) swag.push(a[r++]); if (swag.fold() == 1) res += n - r + 1; swag.pop(); } OUT(res); }