Subtask 1

Let's imagine the array as a line of nodes. We add a directed edge from ~x~ to ~y~ if ~x~ should be at the current position of ~y~ in the optimal solution. For example, the graph representing the solution to the sample case is shown below, with different colours distinguishing different groups of indices selected in the sorting process:

By the definition of lexicographical minimum, we want to minimize the value of the first element, then the second, and so on. Therefore, the first thing we want to do is to draw an edge from ~1~ to the element at the first index. Then, similarly for ~2~, we want to draw an edge from it to the element at the second index. If this isn't possible, we will try ~3~, then ~4~, then ~5~, etc. In general, for each index, we want the smallest element possible pointing to that index.

Note that as we move through this process, we will form chains of directed edges connecting the nodes together. We know that it is possible to draw an edge from ~x~ to ~y~ if it falls into one of these two categories:

• ~x~ and ~y~ are part of different chains, and the combined number of nodes in the ~2~ chains does not exceed ~K~.
• ~x~ and ~y~ are part of the same chain, and connecting ~x~ to ~y~ completes a directed cycle.

It is possible to directly simulate this process with a nested for-loop, maintaining the necessary information with DSU.

Time Complexity: ~\mathcal{O}(N^2)~

Subtask 2

Instead of the inner for-loop from the previous solution, we can simulate it with a segment tree indexed by values that stores the size of the component for each value (for example, ~\text{tree}[i]~ stores the size of the chain containing the element ~i~). For each iteration ~i~ of the outer loop, we are looking for the least index in the segment tree with a value no greater than ~K - sz[i]~ where ~sz[i]~ is the size of the component of ~i~. This can easily be found in ~\mathcal{O}(\log N)~ time by walking down the segment tree if we store the minimum of all values in each node of the segment tree.

Time Complexity: ~\mathcal{O}(N \log N)~