Given a number
N (
\(1<=N<=1000\)) followed by
N natural numbers from
1 to
100.
Output the permutation of the array elements on which quicksort will perform the maximum number of comparisons, provided that
"reference" there will be an element in the middle.
Input
The first line specifies the number
N.
Imprint
Output the desired permutation of numbers from
1 to
N, on which quicksort will perform the maximum number of comparisons.
Examples
| # |
Input |
Output |
| 1 |
5 |
1 4 5 3 2 |
Explanation
The worst running time is when the array is split so that one part contains n−1 elements and the second — 1. This can be achieved if at each stage of the split there is a maximum element in the middle.
1)
1 4 5 3 2
2)
1 4 2 3 5
3)
1 3 2 4 5
4)
1 2 3 4 5
5)
1 2 3 4 5