Background

As everyone knows, a coconut is a coconut, but this seems to have nothing to do with the problem.

Problem Description

You are given a sequence $a$ of length $n$. We guarantee that every number from $1$ to $n$ appears in $a$ exactly once. For each $1\le i\le n$, after changing the value $i$ in the sequence to $1$, find how many different subarray $\gcd$ values the sequence has.

More precisely, let $A^x$ be the sequence after changing the number with value $x$ to $1$. Define the set $S_x=\{\gcd\limits_{i=l}^r(A^x_i)|1\le l\le r\le n\}$. Compute $|S_i|$ for all $i$.

Input Format

The first line contains a positive integer $n$, the length of the permutation.

The next line contains $n$ positive integers, the sequence $a$.

Output Format

Output one line with $n$ integers in total. The $i$-th integer denotes the number of different subarray $\gcd$ values after changing the number with value $i$ to $1$.

3
3 1 2

3 2 2

6
3 6 4 1 5 2

6 6 5 5 5 5

Hint

Sample Explanation 1

After changing $1$ to $1$, there are $3$ different subarray $\gcd$ values: $\{1,2,3\}$. They can correspond to subarrays $[1,3]$, $[3,3]$, and $[1,1]$, respectively.

After changing $2$ to $1$, there are $2$ different subarray $\gcd$ values: $\{1,3\}$. They can correspond to subarrays $[2,3]$ and $[1,1]$, respectively.

After changing $3$ to $1$, there are $2$ different subarray $\gcd$ values: $\{1,2\}$. They can correspond to subarrays $[1,2]$ and $[3,3]$, respectively.

Constraints and Notes

This problem uses bundled testdata.

$A$: For all $1\le i\le n$, we have $a_i=i$.

For all testdata, $2\le n\le 5\times 10^5$. We guarantee that every number from $1$ to $n$ appears in $a$ exactly once.

Translated by ChatGPT 5