-->

## Restore Sequence codechef  november  long challenge  problem solution -

Restore Sequence codechef  november  long challenge  problem solution  lets read problem statement.

Alice has a very complex machine ― when fed with a sequence ${A}_{1},{A}_{2},\dots ,{A}_{N}$, it produces a sequence ${B}_{1},{B}_{2},\dots ,{B}_{N}$, where for each valid $i$${B}_{i}$ is the largest index $j$ such that ${A}_{i}$ divides ${A}_{j}$ (since ${A}_{i}$ divides itself, such an index always exist). For example, if the machine is fed with $A=\left[2,6,5,3,4\right]$, it produces $B=\left[5,2,3,4,5\right]$.

Alice gave you a sequence $B$ that was produced by the machine. Find an integer sequence $A$ such that when it is fed into the machine, then the machine produces the sequence $B$. Alice does not like huge integers, so make sure that $1\le {A}_{i}\le 4\cdot {10}^{6}$ holds for each valid $i$.

### Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of each test case contains a single integer $N$.
• The second line contains $N$ space-separated integers ${B}_{1},{B}_{2},\dots ,{B}_{N}$.

### Output

For each test case, print a single line containing $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$. For each valid $i$$1\le {A}_{i}\le 4\cdot {10}^{6}$ should hold.

If there are multiple solutions, you may print any of them. It is guaranteed that at least one solution exists.

### Constraints

• $1\le T\le 2\cdot {10}^{4}$
• $1\le N\le {10}^{5}$
• $1\le {B}_{i}\le N$ for each valid $i$
• the sum of $N$ over all test cases does not exceed $2\cdot {10}^{5}$

Subtask #1 (20 points): ${B}_{1},{B}_{2},\dots ,{B}_{N}$ are pairwise distinct

Subtask #2 (80 points): original constraints

### Example Input

2
5
5 2 3 4 5
4
4 4 4 4


### Example Output

2 6 5 3 4
2 6 3 12

link-https://www.codechef.com/NOV20B/problems/RESTORE

### Restore Sequence codechef Solution -

read also -https://www.technicalkeeda.in/2020/11/magical-candy-problem-solution-codechef.html

Logic-
It's necessary that b[i]>=i
let's assume my final ans is 2*n,2n-1,2n-2,2n-3...........n+1
I choose this initial sequence because ith element of this sequence cannot divide any other incoming element of this sequence.
store this sequence into a final answer vector
Now you have to change this sequence in such a way it can produce given B.
Now start iterating given array B.
Now change final ans like this
int k=v[i];
if(v1[i]>v1[k-1]){
v1[k-1]=v1[i];
}
else{
v1[i]=v1[k-1];
}

Finally, print ans vector.
Note-
This question can be done by another approach.

Must Join Telegram channel for Editorial -

My code-