H-你怎么知道我玩原神还是玩刻晴的？_新疆大学2025年7月月赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

对正整数集合 $S$ ，定义 $\operatorname{mex^+}\{S\}$ 为 $\operatorname{mex}\{S\cup\{0\} \}$ ，其中对于自然数集合 $S$ ， $\operatorname{mex}\{S\}$ 是指 $S$ 中没有出现过的最小的自然数。同样地，定义 $\gcd \{S\}$ 为集合 $S$ 里面所有数的最大公因数。

对下标自 $1$ 始的，有穷正整数数列 $\{A_i\}$ ，定义 $|\{A_i\}|$ 为其大小， $A[l,r](1\le l \le r \le |A|)$ 为集合 $\{A_i|i\in[l,r]\}$ 。

给定长度为 $n$ 的正整数数列 $\{a_i\}$ ，问有多少对 $[l,r](1\le l \le r \le n)$ 满足： $\gcd\{a[l,r]\}=\operatorname{mex^+}\{a[l,r]\}$ 。

输入描述:

输入文件的第一行为一个正整数  表示正整数数列  的长度。

接下来一行  个正整数，第  个正整数表示 ，保证 。

输出描述:

输出一行一个整数表示答案。

示例1

输入

复制

6
1 1 4 5 1 4

输出

复制