Consider the array $a_1,a_2,\dots ,a_N$ and consider two indices $i,j$ with $i<j$. Let $x$ be the number of elements in the subarray from $i$ to $j$ with value between $a_i$ and $a_j$ exclusive. Consider how the number of inversions changes if the elements with indices $i$ and $j$ are swapped. It turns out that if $a_i<a_j$, then the number of inversions increases by $1+2\cdot u$ and if $a_i>a_j$, then the number decreases by $1+2\cdot u$. So $u$ can be determined by swapping $i$ and $j$.

Observe that if $i=1$ and $j=N$, then the subarray from $1$ to $N$ contains every number from $1$ to $N$. So the value $u+1$ is simply the difference between $a_i$ and $a_j$. We will extend this idea. First, set $i=1,j=N$. This tells us $a_N$ relative to $a_1$. Next, set $i=1,j=N-1$. Though the subarray from $1$ to $N-1$ is no longer every number, we know the value of $a_N$ relative to $a_1$ and $a_N$ is the only missing number. So we can determine $a_{N-1}$ relative to $a_1$. We continue this with $j=N-2,N-3,\dots ,2$ to determine every element of the array relative to each other. Using this, each element can be identified. This took $N-1$ swaps (plus another at the start to get the initial number of inversions). Once the elements are known, it is easy to sort the array in $N-1$ swaps. This totals to $2N-1$ which is just barely under the limit.

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