#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; ll op(ll a, ll b) { return gcd(a, b); } ll e() { return 0; } int main() { int n; cin >> n; vector a(n); rep(i, 0, n) cin >> a[i]; segtree st(a); ll ans = 0; for (int i = 0; i < n; i++) { if (st.prod(i, n) != 1) break; int l = i, r = n; while (r - l > 1) { int m = (l + r) / 2; if (st.prod(i, m) == 1) r = m; else l = m; } ans += n - r + 1; } cout << ans << endl; }