Max-Heap

Limit czasu: 1s | Limit pamięci: 64MB

Dany jest ciąg liczb $a_1, a_2, \ldots, a_n$. Uporządkuj te elementy w taki sposób, aby stanowiły kopiec typu max, tzn. zastosuj poniższy algorytm:

	// Cormen et al. - Introduction to Algorithms
	buildMaxHeap(A)
		for i = n/2 downto 1
		maxHeapify(A, i)

	maxHeapify(A, i)
		l = left(i)
		r = right(i)
	  	
		// select the node which has the maximum value
		if l <= n and A[l] > A[i]
	    		largest = l
		else 
	    		largest = i
		if r <= n and A[r] > A[largest]
	    		largest = r

		if largest != i　// value of children is larger than that of i
			swap A[i] and A[largest]
			maxHeapify(A, largest) // call recursively

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$. Drugi wiersz zawiera $n$ liczb $a_i$.

Wyjście

Pierwszy i jedyny wiersz wyjścia zawiara ciąg $n$ elementów $a_i$ w kolejności wyznaczonej przez algorytm buildMaxHeap.

Ograniczenia

• $1 \le n \le 500 000$
• $-2 \cdot 10^9 \le a_i \le 2 \cdot 10^9$

Przykłady

Wejście 1

10
4 1 3 2 16 9 10 14 8 7

Wyjście 1

16 14 10 8 7 9 3 2 4 1