Prahova Valley

Andrei's route to the IIOT finals begins in the famous Prahova Valley! During the road trip, he got bored and came up with the following algorithm (note: we denote the assignment operation as $x \gets y$):

for i ← N … 1 do
    j ← i + 1
    while j ≤ N and Vⱼ % Vᵢ = 0 do
        j ← Rⱼ
    end while
    Rᵢ ← j
end for

During a brief stop at the famous Peleș Castle in Sinaia, he wrote down all the house numbers he found around the city and applied the aforementioned algorithm. He wrote down the resulting sequence $R$ on a separate sheet of paper.

Task

When Andrei gets into the car, he realizes that he has lost all the pages of his notebook except the ones containing sequence $R$ and the algorithm.
Your task is to find the lexicographically smallest sequence $V$ of $N$ integers such that applying the algorithm to $V$ produces the sequence $R$.

Input data

The first line of the input contains the integer $N$, representing the number of integers in the $R$ sequence.

The second line of the input contains $N$ space-separated integers $R_1, R_2, \ldots, R_N$, representing the elements of the $R$ sequence.

Due to the high volume of input data, we recommend adding the following lines before reading any input:

ios_base::sync_with_stdio(false);
cin.tie(0);

Output data

The first line of the output must contain $N$ space-separated integers $V_1, V_2, \ldots, V_N$, representing the lexicographically smallest sequence such that applying the algorithm to it produces sequence $R$.

Constraints and clarifications

• $1 \leq N \leq 5 \ 000 \ 000$
• $i + 1 \leq R_i \leq N + 1$, for all $1 \leq i \leq N$
• We guarantee that, for the given input, there is always a solution.
• $1 \leq V_i \leq 2^{50}$, for all $1 \leq i \leq N$
• The algorithm produces the same result regardless of the initial values of $R_i$, meaning we can safely assume $R_i = 0$ for all $1 \leq i \leq N$.
• We define array $A$ as being lexicographically smaller than array $B$ (both of size $K$) if, for some index $p$ where $0 \le p < K$, the prefixes of length $p$ are identical ($A_i = B_i$ for all $1 \le i \le p$) and the $(p+1)$-th elements satisfy $A_{p+1} < B_{p+1}$.

Example

stdin

5
6 5 4 5 6

stdout

1 2 4 2 1

Explanation

We will apply the algorithm on $\{1, 2, 4, 2, 1\}$.

• $i = 5$: The pointer $j$ is initialized to $6$. Since $j \ge N+1$, the inner loop condition is not met, resulting in $R_5 = 6$.
• $i = 4$: Initializing $j = 5$, we find that $V_5 \ \% \ V_4 \neq 0$. The loop terminates immediately, setting $R_4 = 5$.
• $i = 3$: Starting with $j = 4$, we check $V_4 \ \% \ V_3 \neq 0$, thus $R_3 = 4$.
• $i = 2$: We begin with $j = 3$. Since $V_3 \ \% \ V_2 = 0$, we update $j \gets R_3 = 4$. Subsequently, as $V_4 \ \% \ V_2 = 0$, we update $j \gets R_4 = 5$. Finally, $V_5 \ \% \ V_2 \neq 0$, yielding $R_2 = 5$.
• $i = 1$: Starting with $j = 2$, we perform the following updates:
  • $V_2 \ \% \ V_1 = 0 \implies j \gets R_2 = 5$.
  • $V_5 \ \% \ V_1 = 0 \implies j \gets R_5 = 6$.

The loop terminates as $j=6$, resulting in $R_1 = 6$.

We can show that this is the lexicographically smallest solution for the given input.