You should find the permutation with the maximum number of inversions. You can use segment tree to calculate inversions for each element, just store sorted leafes in each node.