Unsorting a Sequence 1

If all values are equal, every rearrangement is sorted. Otherwise sorting in nonincreasing order gives a strict descent and a valid answer. Time is $O(N\log N)$. The small subtask can enumerate permutations.