For each integer \(k=1,2,\dots,N\), let \(L_k\) and \(R_k\) be the smaller and larger of the two \(i\)’s such that \(A_i=k\), respectively.

[1] The number of operations required to make a good sequence

First, consider how many operations are required to make \(A\) a good sequence.

This can be calculated similarly to the inversion number if we fix the resulting good sequence, and if we particularly consider the contributions to the number of operations based on the positional relationship of the two types of integers, we can classify them into the following three patterns:

• \((\dots,1,\dots,1,\dots,2,\dots,2,\dots) \rightarrow (\dots,1,1,\dots,2,2,\dots) \) or \((\dots,2,2,\dots,1,1,\dots) \)

• \((\dots,1,\dots,2,\dots,1,\dots,2,\dots) \rightarrow (\dots,1,1,\dots,2,2,\dots) \) or \((\dots,2,2,\dots,1,1,\dots) \)

• \((\dots,1,\dots,2,\dots,2,\dots,1,\dots) \rightarrow (\dots,1,1,\dots,2,2,\dots) \) or \((\dots,2,2,\dots,1,1,\dots) \)

If we calculate the contribution for each of these, we find that it is basically better to have the smaller \(i\) with \(L_i\) on the left. Therefore, sorting the pairs in \(A\) in ascending order of \(L_i\) achieves the minimum number of operations required to make a good sequence.

[2] Lexicographical minimization

Based on the consideration in [1], let’s consider lexicographically minimizing the sequence. For the first and second patterns of positional relationship in \(A\) above, the optimal arrangement is uniquely determined, but for the third pattern, either is fine. Thus, when determining the terms of the resulting good sequence one by one from the left, what can be placed as the next term among the integers \(k\) that have not yet appeared are the ones such that \(R_{k} < R_{k'}\) for every \(k'\) satisfying \(L_{k'} < L_k\).

Based on this, let’s organize the process to find the answer. Let \(P\) be a permutation \(P\) of integers from \(1\) to \(N\) such that \(L_{P_i} < L_{P_{i+1}}\). If we perform the following to determine the terms of the resulting good sequence one by one from the left, we will find the lexicographically smallest good sequence \(ans\).

• Initialize an integer sequence \(X\) as \(X=(P_1,P_2,\dots,P_N)\). Also, initialize the sequence \(ans\) as \(ans=()\).
• Repeat the following operation \(N\) times:
  • Add to \(ans\) twice the smallest value \(x\) among the \(X_k\)’s such that \(\displaystyle \min_{1 \leq i \leq k} R_{X_i} = R_{X_k}\). Then, remove \(x\) from \(X\).

A naive implementation of this will take \(\Theta (N^2)\) time in the worst case.

Let us call an \(X_k\) such that \(\displaystyle \min_{1 \leq i \leq k} R_{X_i} = R_{X_k}\) a “low term.” Once \(X_k\) becomes a low term, it will always be a “low term”. Therefore, if you can quickly detect the low terms that newly arise when a term is removed from \(X\), you can perform the above process quickly by managing the low terms with a priority queue.

[3] Segment tree to detect low terms

The above-mentioned deletion of terms and the detection of low terms can be done quickly with a segment tree that manages the following:

• Value 1: The minimum value of \(R_{X_k}\) in the interval
• Value 2: The minimum value of \(R_{X_k}\) for \(X_k\) that would be a low term when only considering the interval but is not a low term in the entire sequence (\(\infty\) if it does not exist)

(Note: For Value 2, it says “not a low term in the entire sequence”, but to be precise, it should be “not a detected low term in the entire sequence.”)

First, the deletion of terms can be substituted by updating \(R_{X_k}\) to \(\infty\) (in other words, updating Value 1 of the leaf node corresponding to \(k\) to \(\infty\)). Then, for the detection of a new low term, if Value 2 of the node managing the entire sequence is not \(\infty\), we find that a new low term has arisen due to deletion. Since Value 2 considers \(X_k\)’s that are not low terms in the entire sequence, it is necessary to update the segment tree also when a new low term is detected, and this can be done by updating Value 2 of the leaf node corresponding to \(k\) to \(\infty\).

For details on the implementation, see this.

Since the deletion of terms and the update of the segment tree associated with the low terms occur \(O(N)\) times, the answer can be found in a total of \(O(N\log N)\) time.