// ---------- begin Foldable Queue ---------- struct FoldableQueue { front: Vec<(T, T)>, back: Vec<(T, T)>, op: F, } #[allow(dead_code)] impl FoldableQueue where T: Clone, F: Fn(&T, &T) -> T, { fn new(op: F) -> Self { FoldableQueue { front: Vec::new(), back: Vec::new(), op: op, } } fn find(&self) -> Option { match (self.front.last(), self.back.last()) { (Some(a), Some(b)) => Some((self.op)(&a.1, &b.1)), (Some(a), None) => Some(a.1.clone()), (None, Some(b)) => Some(b.1.clone()), (None, None) => None, } } fn clear(&mut self) { self.front.clear(); self.back.clear(); } fn len(&self) -> usize { self.front.len() + self.back.len() } fn push_back(&mut self, val: T) { let sum = if let Some(p) = self.back.last() { (self.op)(&p.1, &val) } else { val.clone() }; self.back.push((val, sum)); } fn push_front(&mut self, val: T) { let sum = if let Some(p) = self.front.last() { (self.op)(&val, &p.1) } else { val.clone() }; self.front.push((val, sum)); } fn pop_front(&mut self) -> Option { if self.len() == 0 { return None; } if self.front.is_empty() { let mut a = std::mem::take(&mut self.back); for v in a.iter().rev() { self.push_front(v.0.clone()); } a.clear(); self.back = a; } self.front.pop().map(|p| p.0) } } // ---------- end Foldable Queue ---------- use std::io::Read; // ---------- begin binary_gcd ---------- pub fn gcd(a: u64, b: u64) -> u64 { if a == 0 || b == 0 { return a + b; } let x = a.trailing_zeros(); let y = b.trailing_zeros(); let mut a = a >> x; let mut b = b >> y; while a != b { let x = (a ^ b).trailing_zeros(); if a < b { std::mem::swap(&mut a, &mut b); } a = (a - b) >> x; } a << x.min(y) } // ---------- end binary_gcd ---------- fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let n: usize = it.next().unwrap().parse().unwrap(); let a: Vec = it.map(|s| s.parse().unwrap()).collect(); let mut deq = FoldableQueue::new(|a, b| gcd(*a, *b)); let mut ans = 0usize; let mut r = 0; for i in 0..n { if r == i { deq.push_back(a[r]); r += 1; } while r < n && deq.find().unwrap() > 1 { deq.push_back(a[r]); r += 1; } if deq.find().unwrap() == 1 { ans += n + 1 - r; } deq.pop_front(); } println!("{}", ans); } fn main() { run(); }