Let's consider the first (leftmost) shoe ~A~ in the line and its matching shoe (that is, the shoe, that this one will be paired with in an optimal arrangement). Let's suppose that the matching shoe is initially at position ~k~ (~k \ge 1~). Each possible swap either involves moving at least one of these two shoes or does not involve moving any of them. Swaps of the first kind do not affect the relative ordering of all the other shoes. At the same time, swaps of the second kind do not affect the two shoes in question, which means that in order to pair up these two shoes there should be at least ~k-1~ swaps of the first kind, in case the leftmost shoe is a left shoe, or ~k~ swaps, if it's a right shoe. Regardless of how swaps of the second kind are going to advance, we could initially perform this set of ~k-1~ or ~k~ swaps, moving the shoe initially located at position ~k~ to the left until the pair occupies the two leftmost positions.

The greedy approach is optimal since the pair of shoes handled in this way will not interfere with any further swaps. Moreover, it always makes sense to take the leftmost one among the shoes matching shoe ~A~, since otherwise the same intermediate arrangement with the two leftmost positions occupied by a matching pair of shoes could be obtained by an even shorter sequence of swaps: if another matching shoe is at position ~k' > k~, then instead of moving ~k'~ all the way to the left, first move it until the shoe occupies position ~k+1~, but then instead of moving it further, simply start moving the shoe that was at position ~k~.

The process can be repeated until the arrangement of the shoes becomes valid. This can be modelled naively in quadratic time, which solves most of the subtasks, or more efficiently in ~\mathcal O(n \log n)~ using a Fenwick tree or a segment tree.