You are given an array $$$a$$$ of length $$$n$$$. Notice that array can contain dupilcate elements.

You can perform the following operation:

• choose two integers $$$i$$$, $$$j$$$ such that $$$1\leq i,j \leq n$$$
• swap $$$a_i$$$ and $$$a_j$$$

Find the minimum number of operations to sort the array.

It seems like a very natural problem, but I didn't find any solutions to it. Does anyone know the solution?

Some thoughts:

Let $$$a'$$$ be an array $$$a$$$ after sorting. Let's consider a graph $$$G$$$ with edges $$$a'[i] \rightarrow a[i]$$$. So now we need to somehow decompose this graph into cycles, such that the number of cycles is maximum.

To do that we can notice that $$$G$$$ is an euliran graph so we can find an euler cycle of it (let's store it in array $$$p$$$). Now each cycle in $$$G$$$ is some segment in $$$p$$$ which starts and ends in the same number (actually it can be circural segment). So we have some segments in $$$p$$$ and we need to find the maximum number of segments, such that they do not intersect (but they can lie inside each other and touch). This problem seems like some dp on segments, but I didn't figure it out yet.