Let \(A=(a_1,a_2, \ldots,a_N), B=(a_{N+1}, \ldots, a_{2N})\).

Also, let \(\mathrm{X}\) be \(\min(A)\).

If there is \(i\) such that \(A_i=\mathrm{X}, A_i \geq B_i\), choosing such \(i\) with the smallest \(B_i\) yields the lexicographically smallest possible sequence.

Below, we assume \(A_i \leq B_i\) when \(A_i = \mathrm{X}\). Then, it can be proved that all \(i\) such that \(A_i = \mathrm{X}\) are chosen in the optimal solution (otherwise, the resulting sequence will be obviously lexicographically larger).

Let \(y=(y_1, y_2, \ldots, y_K)\) be the list of \(i\) such that \(A_i = \mathrm{X}\) sorted in ascending order. Let us consider the optimal choice of \(j\) such that \(y_K <j \leq N, A_j \leq B_{c_1}\).

Let us deal with these \(j\) after sorting them by \((A_j,j)\) in ascending order. Then, for elements such that \(A_j < B_{y_1}\), it can be shown that the optimal strategy is to add \(j\) if it is greater than the current last element of \(y\) (otherwise, the result will be lexicographically larger).

The last thing to consider is whether to choose \(j\) such that \(A_j = B_{y_1}\). The following can be shown: if adding one such \(j\) makes the result lexicographically smaller, they should be chosen as many as possible. Otherwise, none of them should be chosen.

It is possible to implement the above to find the answer in \(O(N)\) time, but an \(O(N \log N)\) algorithm also runs fast enough.