That doesn't work for the case 4 5 6 7 9 1 10 since you can just switch the 10 and the 1.

The solution is for every number starting from the number with the lowest value, swap it all the way to the left or to the right. You will only swap with the numbers that are greater than it, so you will need store how many numbers are greater than it to the left and how many are greater to the right, which you can do with fenwick tree.

Does anyone know what's wrong with the following solution for bitonic ordering? Spent quite a bit trying to debug/identify the flaw b/c I kept getting the wrong answer. I also could not create a test-case that broke my code:

First, I compressed all values to be in the range [0,n-1], where n is the # of elements.

Now, suppose that index i contains the element with value n-1 (aka maximum in array). From here, it suffices to compute the minimum # of swaps needed to make the left part of the array (a[0] --> a[i-1]) monotonically increasing and the right part of the array (a[i+1] --> a[n-1]) monotonically decreasing.

Now, we traverse from left to right and compute the cost of creating the array such that the max is positioned each possible index i, using two Fenwick Trees to accomplish the task. The answer is the minimum of all such costs.

The complexity is O(NlogN).