题目背景

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

题目描述

给出一个长度为 $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]$。

数据规模与约定

本题采用捆绑测试。

$A$：对于所有 $1\le i\le n$，有 $a_i=i$。

对于所有的数据，$2\le n\le 5\times 10^5$，我们保证 $1\sim n$ 中的每一个数都恰好在 $a$ 中出现了一次。