#include #include using namespace atcoder; using namespace std; using ll = long long; ll op(ll a, ll b) {return gcd(a, b);} ll e() {return 0LL;} int main() { int N;cin >> N; vector A(N + 1, 0); for (int i = 1;i <= N;i++) cin >> A[i]; int r = -1; ll ans = 0; segtree seg(A); for (int i = 1;i <= N;i++) { if (r == -1 or r == i - 1) { ll g = 0; for (int k = i;k <= N;k++) { if (gcd(g, A[k]) == 1) break; g = gcd(g, A[k]); r = k; } if (r == -1) { ans += N - i + 1; } else { ans += N - r; } continue; } ll now = seg.prod(i, r + 1); for (int k = r + 1;k <= N;k++) { if (gcd(A[k], now) == 1) break; r = k; now = gcd(now, A[k]); } ans += N - r; } cout << ans << endl; }