問題文

$N$個の要素からなる数列$A$が与えられます。$i$番目($1\le i\le N$)の要素は$A_i$です。この数列の空ではない連続する部分列を考えます。
含まれる全ての要素の最大公約数が$1$となるような数列$A$の連続する部分列の総数を求めてください。

ある2つの連続する部分列に関して、その要素の値が全て一致しても元の数列における位置が異なるものが含まれている場合、その連続する部分列は異なるものとして扱うことに注意してください。

補足

writer解は、python3ではTLEでした。pypy3ではACを確認しています。
【2020/04/26追記】コンテスト時よりいくつかテストケースを追加し、解説を修正しています。

入力

$N$
$A_1{A}_2\dots A_N$

入力は全て整数である
$1\le N\le 500000$
$1\le A_i\le {10}^{18}(1\le i\le N)$

出力

最後に改行してください。

サンプル

3
1 2 3

4

4
1 1 1 1

10

4
2 4 8 16

0

10
801754 703742 332182 68016 914814 8470 937255 293192 313080 501971

28