Replace Non-Coprime Numbers in Array

Maintain a stack representing the reduced prefix. For each incoming number, push it. While the stack has at least two values, compute g = gcd(stack[-2], stack[-1]). If g == 1, the top pair is coprime and no merge is possible at that boundary. Otherwise pop both values, compute their least common multiple as (a / g) * b, push that merged value, and continue the loop because it may now be non-coprime with the preceding stack value. The repeated check is the key to handling cascades.

The stack invariant is that every adjacent pair below the top is already coprime. A merge can only invalidate the boundary immediately before the new top, so no earlier pairs need to be rescanned. Divide before multiplying to reduce overflow risk, and use the integer width required by the problem constraints. Test already coprime arrays, a chain that merges repeatedly, duplicates, and values containing large common factors. With bounded integer arithmetic, each input is pushed once and removed through merges, giving amortized O(n log M) time for gcd work, where M bounds values, and O(n) space.