P10916 Coconut.

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

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$.

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

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$.

### 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**. | $\text{Subtask}$ | Score | Constraints | Special Property | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $n\le 20$ | No special restrictions. | | $2$ | $20$ | $n\le 200$ | No special restrictions. | | $3$ | $30$ | $n\le 2000$ | No special restrictions. | | $4$ | $20$ | No special restrictions. | $A$. | | $5$ | $20$ | No special restrictions. | No special restrictions. | $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