椰子

众所周知，椰子是一种椰子，但这和题目好像没什么关系。

给出一个长度为 $n$ 的序列 $a$，我们保证 $1\sim n$ 中的每一个数都恰好在 $a$ 中出现了一次，对于每一个 $1\le i\le n$，求出在序列中将值为 $i$ 的数的值修改成 $1$ 后，序列有多少种不同的区间 $\gcd$ 的值。 严格来说，记将值为 $x$ 的数修改为 $1$ 后的序列为 $A^x$。集合 $S_x=\{\gcd\limits_{i=l}^r(A^x_i)|1\le l\le r\le n\}$，求出所有 $|S_i|$ 的值。

第一行一个正整数 $n$，表示排列的长度。 接下来一行 $n$ 个正整数，表示序列 $a$。

一行一共 $n$ 个整数，第 $i$ 个数表示在把值为 $i$ 的数改成 $1$ 后，序列有多少种不同的区间 $\gcd$ 的值。

3
3 1 2

3 2 2

6
3 6 4 1 5 2

6 6 5 5 5 5

### 样例解释 1 对于将 $1$ 变成 $1$，有 $\{1,2,3\}$ 共 $3$ 种不同的区间 $\gcd$ 值，分别可以对应区间 $[1,3],[3,3],[1,1]$。 对于将 $2$ 变成 $1$，有 $\{1,3\}$ 共 $2$ 种不同的区间 $\gcd$ 值，分别可以对应区间 $[2,3],[1,1]$。 对于将 $3$ 变成 $1$，有 $\{1,2\}$ 共 $2$ 种不同的区间 $\gcd$ 值，分别可以对应区间 $[1,2],[3,3]$。 ### 数据规模与约定 **本题采用捆绑测试**。 | $\text{Subtask}$ | 分数 | 数据范围 | 特殊性质 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $n\le 20$ | 无特殊限制 | | $2$ | $20$ | $n\le 200$ | 无特殊限制 | | $3$ | $30$ | $n\le 2000$ | 无特殊限制 | | $4$ | $20$ | 无特殊限制 | $A$ | | $5$ | $20$ | 无特殊限制 | 无特殊限制 | $A$：对于所有 $1\le i\le n$，有 $a_i=i$。 对于所有的数据，$2\le n\le 5\times 10^5$，我们保证 $1\sim n$ 中的每一个数都恰好在 $a$ 中出现了一次。