Distinct Interval GCDs After Modification

You are given a permutation \(a\) of length \(n\) containing the integers \(1, 2, \dots, n\) in some order. For each \(1 \le i \le n\), define the sequence \(A^i\) as the sequence obtained by replacing the unique occurrence of \(i\) in \(a\) with \(1\) (if it is not already \(1\)).

For a fixed \(i\), let \[ S_i = \{\gcd(A^i_l, A^i_{l+1}, \dots, A^i_r) \mid 1 \le l \le r \le n\}\, \] be the set of greatest common divisors (gcd) for every contiguous subarray of \(A^i\). Your task is to compute \(|S_i|\) for each \(i\) from \(1\) to \(n\), i.e. the number of distinct gcd values that occur among all subarrays of \(A^i\).

Note: \(\gcd(x_1, x_2, \dots, x_k)\) denotes the greatest common divisor of \(x_1, x_2, \dots, x_k\).

inputFormat

The first line contains an integer \(n\) (\(1 \le n\)). The second line contains \(n\) space-separated integers representing the permutation \(a\) of \(1, 2, \dots, n\).

outputFormat

Output a single line containing \(n\) space-separated integers, where the \(i\)-th integer is equal to \(|S_i|\) — the number of distinct gcd values of the subarrays of the sequence \(A^i\) (the sequence obtained after replacing the element equal to \(i\) with \(1\)).

sample

3
3 1 2

3 2 2