Notice that items ~a~ to ~N~ don't have to move if ~[a, N]~ is a subsequence of the array. We can calculate which items don't have to move, and move everything else in order, largest to smallest.

We can use a similar strategy to the first subtask, but on both sides. Colour indices before ~K~ in red, and those after ~K~ in blue. Index ~K~ is purple. Any element in the list which is not in the correct section must be moved to the correct section (~K + 1~, the purple element, is always in the correct section). Start from the side that allows the middle element to land on the correct side. If the middle element is purple, choose the side with more elements.

After the elements are on the correct sides, apply the subtask 1 algorithm to both sides, starting from the side with the purple element.

Thanks to 4fecta for finding this solution.

In a case like 2 5 3 1 4 7 6 with K = 2, the solution for 55% is suboptimal because after moving ~5~ to the right side, it has to be put in place with ~6 5~. However, it would be optimal to simply start with 6 5, and the reference solution outputs 6 1 2 5 4 3 for this case.

Instead of proceeding in two parts, we should sort everything together all at once. Note that doing an operation on an element that resides on the left moves the middle element left, and vice versa. Thus, after moving an element, we need to pick an element from the side corresponding to the colour. For example, after playing ~6~ in the above case, we have to play a move from the right side, or ~6~ will end up on the wrong side.

At the beginning, we can try starting from both sides, whichever one we choose will determine the direction of the element initially at position ~K~. We can simply take the minimum of both answers.

Furthermore, at any time, we only have two good moves. After we calculate the elements that don't need to move (left as an exercise), either the largest element not in place or the smallest one not in place can be played. If, of the two moves, only one is available (because the other would push our middle element in the wrong direction), take it. If both are available, greedily take the one that keeps us on the current side.

If neither are available, use the purple element as a means of resetting. If the purple element is not on the current side, use the other side as the starting side. It can be proven that this always results in an answer.