local ffi = require("ffi") local C = ffi.C ffi.cdef[[ long long atoll(const char*); ]] local function lltonumber(str) return C.atoll(str) end local function getgcd(x, y) while 0LL < x do x, y = y % x, x end return y end local n = io.read("*n", "*l") local a = {} local str = io.read() for w in str:gmatch("%d+") do table.insert(a, lltonumber(w)) end local suf_idx = {} local pre_sum, suf_sum = {}, {} local pre_idx_len, suf_idx_len = 0, 0 local function push(idx) suf_idx_len = suf_idx_len + 1 suf_idx[suf_idx_len] = idx if suf_idx_len == 1 then suf_sum[suf_idx_len] = a[idx] else suf_sum[suf_idx_len] = getgcd(suf_sum[suf_idx_len - 1], a[idx]) end end local function pop() if pre_idx_len == 0 then pre_sum[1] = a[suf_idx[suf_idx_len]] for i = 2, suf_idx_len - 1 do local j = suf_idx[suf_idx_len + 1 - i] pre_sum[i] = getgcd(pre_sum[i - 1], a[j]) end pre_idx_len = suf_idx_len - 1 suf_idx_len = 0 else pre_idx_len = pre_idx_len - 1 end end local function query() if pre_idx_len == 0 then return suf_sum[suf_idx_len] elseif suf_idx_len == 0 then return pre_sum[pre_idx_len] else return getgcd(suf_sum[suf_idx_len], pre_sum[pre_idx_len]) end end local ret = 0 local cur = a[1] local right = 1 push(1) for i = 1, n do if right < i then push(i) right = i cur = a[i] end cur = query() while right <= n and 1LL < cur do right = right + 1 if right <= n then push(right) end cur = query() end ret = ret + n + 1 - right pop() end print(ret)