#include #include long long gcd(long long a, long long b) { if (a == 0) return b; if (b == 0) return a; long long r = a % b; return r ? gcd(b, r) : b; } struct SegmentTree { int n; std::vector node; SegmentTree(const std::vector& A) { n = 1; while (n < A.size()) n *= 2; node.resize(n * 2 - 1); for (int i = 0; i < A.size(); i++) node[i + n - 1] = A[i]; for (int i = n - 2; i >= 0; i--) node[i] = gcd(node[i * 2 + 1], node[i * 2 + 2]); } long long get(int a, int b, int k=0, int l=0, int r=-1) { if (r < 0) r = n; if (r <= a || b <= l) return 0; if (a <= l && r <= b) return node[k]; return gcd( get(a, b, k * 2 + 1, l, (l + r) / 2), get(a, b, k * 2 + 2, (l + r) / 2, r) ); } }; int main() { int N; std::cin >> N; std::vector A(N); for (int i = 0; i < N; i++) std::cin >> A[i]; SegmentTree st(A); long long ans = 0; int i = 0, j = 1; while (i < N) { while (j <= N && st.get(i, j) != 1) j++; ans += N - j + 1; if (++i == j) j++; } std::cout << ans << "\n"; }