import Data.Maybe import Data.List import qualified Data.ByteString.Char8 as BS main=do n<-fst.fromJust.BS.readInteger<$>BS.getLine a<-map(fst.fromJust.BS.readInteger).BS.words<$>BS.getLine print$f (n+1) a [(0,0)] [(0,0)] f n a [] r=f n a (drop 2$scanr (\(e,_) (_,s)->(e,s`gcd`e)) (0,0)$reverse$r) [(0,0)] f n [] ((el,sl):l) ((er,sr):r) |sl`gcd`sr==1=n+f n [] l ((er,sr):r) |otherwise=0 f n (a:as) ((el,sl):l) ((er,sr):r) |sl`gcd`sr==1=n+f n (a:as) l ((er,sr):r) |otherwise=f (n-1) as ((el,sl):l) ((a,sr`gcd`a):(er,sr):r)