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 local function getgcd(x, y) if x == 0LL then return y end if y == 0LL then return x end while 0LL < x do x, y = y % x, x end return y end local function lltonumber(str) if #str < 10 then return 1LL * tonumber(str) else local v1 = str:sub(#str - 8, #str) local v2 = str:sub(1, #str - 9) return 1000000000LL * tonumber(v2) + tonumber(v1) end end local SegTree = {} SegTree.updateAll = function(self) for i = self.stagenum - 1, 1, -1 do local cnt = bls(1, i - 1) for j = 1, cnt do self.stage[i][j] = self.func(self.stage[i + 1][j * 2 - 1], self.stage[i + 1][j * 2]) end end end SegTree.create = function(self, n, func, emptyvalue) self.func, self.emptyvalue = func, emptyvalue local stagenum, mul = 1, 1 self.stage = {} self.stage[1] = ffi.new("int64_t[?]", 2) while mul < n do mul, stagenum = mul * 2, stagenum + 1 self.stage[stagenum] = ffi.new("int64_t[?]", mul + 1) end self.stagenum = stagenum -- for i = 1, mul do self.stage[stagenum][i] = emptyvalue end end SegTree.setSilent = function(self, idx, value) self.stage[self.stagenum][idx] = value end SegTree.right_bound = function(self, left, right) local ret, retpos = self.emptyvalue, left - 1 local stage, l, r = 1, left, right local stagenum = self.stagenum while true do local sz = bls(1, stagenum - stage) while (l - 1) % sz ~= 0 or r + 1 - l < sz do stage = stage + 1 sz = bls(1, stagenum - stage) end local tmp = self.func(ret, self.stage[stage][mce(l / sz)]) if 1LL < tmp then ret, retpos = tmp, l + sz - 1 if retpos == right then break end if l + sz <= r then stage, l, r = 1, l + sz, r else break end else if sz ~= 1 then stage, l, r = stage + 1, l, l + sz - 2 else break end end end return retpos + 1 end SegTree.new = function(n, func, emptyvalue) local obj = {} setmetatable(obj, {__index = SegTree}) obj:create(n, func, emptyvalue) return obj end local n = io.read("*n", "*l") local st = SegTree.new(n, getgcd, 0LL) ffi.cdef[[ long long atoll(const char*); ]] local s = io.read() do local i = 1 for w in s:gmatch("%d+") do st.stage[st.stagenum][i] = C.atoll(w) i = i + 1 end end st:updateAll() local ret = 0 local z = n for i = n, 1, -1 do local p = st:right_bound(i, z) ret = ret + n + 1 - p z = mmi(p, n) end print(ret)