There are a number of sorting algorithms which have different characteristics as follows.

Algorithm	Time Complexity (Worst)	Time Complexity (Average)	Stability	Memory Efficiency	Method	Features
Insertion Sort ALDS1_1_A	O( $N^{2}$ )	O( $N^{2}$ )	〇	〇	Insertion	Can be fast for an almost sorted array
Bubble Sort ALDS1_2_A	O( $N^{2}$ )	O( $N^{2}$ )	〇	〇	Swap
Selection Sort ALDS1_2_B	O( $N^{2}$ )	O( $N^{2}$ )	×	〇	Swap
Shell Sort ALDS1_2_D	O( $N^{2}$ )	O( $N l o g N$ )	×	〇	Insertion
Merge Sort ALDS1_5_A	O( $N l o g N$ )	O( $N l o g N$ )	〇	×	Divide and Conqure	Fast and stable. It needs an external memory other than the input array.
Counting Sort ALDS1_6_A	O( $N + K$ )	O( $N + K$ )	〇	×	Bucket	Fast and stable. There is a limit to the value of array elements.
Quick Sort ALDS1_6_B	O( $N^{2}$ )	O( $N l o g N$ )	×	△	Divide and Conqure	Fast and almost-in-place if it takes a measure for the corner cases. Naive implementation can be slow for the corner cases.
Heap Sort ALDS1_9_D (This problem)	O( $N l o g N$ )	O( $N l o g N$ )	×	〇	Heap structure	Fast and in-place. It is unstable and performs random access for non-continuous elements frequently.

The Heap Sort algorithms is one of fast algorithms which is based on the heap data structure. The algorithms can be implemented as follows.

1  maxHeapify(A, i)
2      l = left(i)
3      r = right(i)
4      // select the node which has the maximum value
5      if l ≤ heapSize and A[l] > A[i]
6          largest = l
7      else 
8          largest = i
9      if r ≤ heapSize and A[r] > A[largest]
10         largest = r
11
12     if largest ≠ i　
13         swap A[i] and A[largest]
14         maxHeapify(A, largest) 
15
16 heapSort(A):
17     // buildMaxHeap
18     for i = N/2 downto 1:
19         maxHeapify(A, i)
20     // sort
21     heapSize ← N
22     while heapSize ≥ 2:
23         swap(A[1], A[heapSize])
24         heapSize--
25         maxHeapify(A, 1)

On the other hand, the heap sort algorithm exchanges non-continuous elements through random accesses frequently.

Your task is to find a permutation of a given sequence $A$ with $N$ elements, such that it is a max-heap and when converting it to a sorted sequence, the total number of swaps in maxHeapify of line 25 in the pseudo code is maximal possible.

Input

In the first line, an integer $N$ is given. In the next line, $A_{i}$ ( $i = 0, 1, . . ., N - 1$ ) are given separated by a single space character.

Output

Print $N$ integers of the permutation of $A$ separated by a single space character in a line.

This problem has multiple solutions and the judge will be performed by a special validator.

Constraints

$1 \leq N \leq 200000$
$0 \leq$ each element of $A$ $\leq 1000000000$
The elements of $A$ are all different

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$0$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签	STL

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战

2700: 9_D : Heap Sort

Description

There are a number of sorting algorithms which have different characteristics as follows.

Input

Input

Output

Output

Sample Input复制

Sample Output复制

提示

Constraints

推荐代码查看2700 所有题解  上传题解视频得图灵币

赛题来源/所属竞赛会津大学《挑战数据结构与算法》挑战数据结构与算法

2700: 9_D : Heap Sort

Description

There are a number of sorting algorithms which have different characteristics as follows.

Input

Input

Output

Output

Sample Input复制

Sample Output复制

提示

Constraints

推荐代码 查看2700 所有题解 var params = { subject: '视频播放', coin_amount:50, word:2700, goods_id: 31 }; 上传题解视频得图灵币

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

推荐代码查看2700 所有题解上传题解视频得图灵币

赛题来源/所属竞赛会津大学《挑战数据结构与算法》挑战数据结构与算法