Given an array of n integers rearrange the values of the array so as to maximize the worth of the array.Worth of an array a is defined as a(n)^(a(n-1)^a(n-2)........(a(1))).You need to print the rearrangement. If multiple answers are possible print the lexicographically largest one.
Example 1:
Input:
N=2
a[]={2,3}
Output:
a[]={2,3}
Explanation:
Since in total 2 permutations are possible {2,3} and
{3,2} the former one has a value of 9 while the latter
one has 8 hence the answer is the former permutation.

Example 2:
Input:
N=3
a[]={1,1,1}
Output:
a[]={1,1,1}
Explanation:
All permutations will yield the same result.

Your Task:
You don't need to read input or print anything. Your task is to complete the function rearrange() which takes the array arr[], its size N, and returns the rearranged array.

Expected Time Complexity: O(NLogN)
Expected Auxiliary Space: O(N)

Constraints:
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{5}
Array may contain duplicate elements.

见题面

见题面