local mfl, mce = math.floor, math.ceil local mmi, mma = math.min, math.max local bls, brs = bit.lshift, bit.rshift local ffi = require("ffi") local C = ffi.C ffi.cdef[[ long long atoll(const char*); ]] local function getgcd1(x, y) while x ~= -x do x, y = y % x, x end return y end local function getgcd2(x, y) if x < y then while x ~= -x do if y < x + x then x, y = y - x, x else x, y = y % x, x end end return y else while y ~= -y do -- while 0LL < y do if x < y + y then y, x = x - y, y else y, x = x % y, y end end return x end end local n = io.read("*n", "*l") local roundcnt = 1 do local mul = 1 while mul < n do roundcnt = roundcnt + 1 mul = mul * 2 end end local len = {} do local tmp, c = 1, 1 for i = 1, n + 1 do if tmp < i then tmp, c = tmp * 2, c + 1 end len[i] = c end end local dp = {} for i = 1, roundcnt do dp[i] = {} for j = 1, n do dp[i][j] = 1LL end end local s = io.read() do local i = 1 for w in s:gmatch("%d+") do dp[1][i] = C.atoll(w) i = i + 1 end end -- print(os.clock()) for i = 2, roundcnt do local jump = bls(1, i - 2) local dpi = dp[i] local dpim1 = dp[i - 1] for j = 1, n - jump do dpi[j] = getgcd1(dpim1[j], dpim1[j + jump]) end end -- print(os.clock()) local function solve(l, r) if dp[1][l] == 1LL then return l end local cur = 0LL local tmp = 0LL while 1 < r - l do local stage = len[1 + r - l] - 1 tmp = getgcd2(cur, dp[stage][l]) if tmp == 1LL then r = l + bls(1, stage - 1) - 1 else cur = tmp l = l + bls(1, stage - 1) - 1 end end return l + 1 end local ret = 0 local z = n + 1 for i = n, 1, -1 do local p = solve(i, z) ret = ret + mma(0, n + 1 - p) end print(ret) -- print(os.clock())