There is a simpler algorithm for this problem.
For every set of 3 consecutive elements, replace the first and third with double of the middle one. Resulting array will have adjacent elements with GCD of 2.
We will meet both the constraints of the problem. We will not replace more than 2/3rd of the elements (since this number is rounded up in the problem statement) and no element in the new array will exceed 1e6 since we are multiplying it by 2.