### 问题描述 过年的时候小蓝收到了 $n$ 个亲戚给的 $a[i]$ 的压岁钱，小蓝发现得到的压岁钱数列存在某种 gcd（最大公约数）关系。 对一个数列 ${a[1],a[2],...,a[k]}$，若存在子数列 $(1 \leq l \leq r \leq k)$，它的 $gcd(a[l],a[l+1],...,a[r]) == r-l+1$ 时，小蓝会很不开心，因此她会要求亲戚重新给红包，使得数列 ${a[1],a[2],...,a[k]}$ 不存在这样的 $l, r$，当然她想让更少的亲戚重新给红包。 现在，小蓝想知道对每个数列 ${a[1],a[2],...,a[i]}$，她最少需要重新得到多少红包。 ### 输入格式 第一行一个 $n(1 \leq n \leq 2 \times 10^{5})$。 第二行 $n$ 个数 $a[i]$，表示亲戚给的红包。$ 1 \leq a[i] \leq 10^{5}$。 ### 输出格式 对每个 $i$ 输出一个答案。 ### 样例输入 ``` 3 1 4 2 ``` ### 样例输出 ``` 1 1 2 ``` ### 提示 对 $i=1: [1] \rightarrow [2]$， 对 $i=2: [1,4] \rightarrow [3,4]$， 对 $i=3: [1,4,2] \rightarrow [2,3,2]$。 ### 评测数据规模 $ 1 \leq n \leq 2 \times 10^{5}$，$ 1 \leq a[i] \leq 10^{5} $。