package main import ( "bufio" "fmt" stdio "io" "os" "strconv" ) // from https://atcoder.jp/users/ccppjsrb var io *Iost type Iost struct { Scanner *bufio.Scanner Writer *bufio.Writer } func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost { const BufSize = 2000005 scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, BufSize), BufSize) return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)} } func (io *Iost) Text() string { if !io.Scanner.Scan() { panic("scan failed") } return io.Scanner.Text() } func (io *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x } func (io *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x } func (io *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x } func (io *Iost) NextInt() int { return io.Atoi(io.Text()) } func (io *Iost) NextInt64() int64 { return io.Atoi64(io.Text()) } func (io *Iost) NextFloat64() float64 { return io.Atof64(io.Text()) } func (io *Iost) Print(x ...interface{}) { fmt.Fprint(io.Writer, x...) } func (io *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(io.Writer, s, x...) } func (io *Iost) Println(x ...interface{}) { fmt.Fprintln(io.Writer, x...) } func main() { in := os.Stdin out := os.Stdout io = NewIost(in, out) defer func() { io.Writer.Flush() }() n := io.NextInt() nums := make([]E, n) for i := 0; i < n; i++ { nums[i] = io.NextInt() } io.Println(solve(nums)) } func solve(nums []int) int { n := len(nums) res := 0 seg := NewSegmentTree(nums) for left := 0; left < n; left++ { right := seg.MaxRight(left, func(x int) bool { return x != 1 }) res += n - right } return res } type E = int func (*SegmentTree) e() E { return 0 } func (*SegmentTree) op(a, b E) E { for b != 0 { a, b = b, a%b } return a } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } type SegmentTree struct { n, size int seg []E } func NewSegmentTree(leaves []E) *SegmentTree { res := &SegmentTree{} n := len(leaves) size := 1 for size < n { size <<= 1 } seg := make([]E, size<<1) for i := 0; i < n; i++ { seg[i+size] = leaves[i] } for i := size - 1; i > 0; i-- { seg[i] = res.op(seg[i<<1], seg[i<<1|1]) } res.n = n res.size = size res.seg = seg return res } func (st *SegmentTree) Get(index int) E { if index < 0 || index >= st.n { return st.e() } return st.seg[index+st.size] } func (st *SegmentTree) Set(index int, value E) { if index < 0 || index >= st.n { return } index += st.size st.seg[index] = value for index >>= 1; index > 0; index >>= 1 { st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1]) } } // [start, end) func (st *SegmentTree) Query(start, end int) E { if start < 0 { start = 0 } if end > st.n { end = st.n } if start >= end { return st.e() } leftRes, rightRes := st.e(), st.e() start += st.size end += st.size for start < end { if start&1 == 1 { leftRes = st.op(leftRes, st.seg[start]) start++ } if end&1 == 1 { end-- rightRes = st.op(st.seg[end], rightRes) } start >>= 1 end >>= 1 } return st.op(leftRes, rightRes) } func (st *SegmentTree) QueryAll() E { return st.seg[1] } // 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MaxRight(left int, predicate func(E) bool) int { if left == st.n { return st.n } left += st.size res := st.e() for { for left&1 == 0 { left >>= 1 } if !predicate(st.op(res, st.seg[left])) { for left < st.size { left <<= 1 if predicate(st.op(res, st.seg[left])) { res = st.op(res, st.seg[left]) left++ } } return left - st.size } res = st.op(res, st.seg[left]) left++ if (left & -left) == left { break } } return st.n } // 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MinLeft(right int, predicate func(E) bool) int { if right == 0 { return 0 } right += st.size res := st.e() for { right-- for right > 1 && right&1 == 1 { right >>= 1 } if !predicate(st.op(st.seg[right], res)) { for right < st.size { right = right<<1 | 1 if predicate(st.op(st.seg[right], res)) { res = st.op(st.seg[right], res) right-- } } return right + 1 - st.size } res = st.op(st.seg[right], res) if right&-right == right { break } } return 0 }