Heapify the Heap (हीप को सही करना)

हीप (Heap) पर मुख्य रूप से दो ऑपरेशन्स किए जा सकते हैं: एक तत्व जोड़ना और हीप से रूट नोड हटाना।

प्रत्येक ऑपरेशन के बाद यह सुनिश्चित करना ज़रूरी है कि हीप की प्रॉपर्टी (heap property) का उल्लंघन न हो।

रूट को हटाते समय, हमें ऊपर से नीचे तक हीप को संशोधित करते हुए उसकी संरचना को दुरुस्त करना होता है, ताकि (मैक्स-हीप (max-heap) के लिए) हर पेरेंट नोड अपने चाइल्ड नोड्स से बड़ा हो।

जब कोई नया तत्व जोड़ना हो, तो नीचे से सबसे ऊपर तक जांच कर, जरूरत पड़ने पर इसलिए स्वैप करें, ताकि पेरेंट नोड अपने चाइल्ड नोड से हमेशा बड़ा हो (मैक्स-हीप के लिए)।

Insert a New Element Into a Heap

किसी नए मान को जोड़ने के लिए, पहले उस मान को एरे (array) के अंत में जोड़ते हैं। उसके बाद, यदि हीप प्रॉपर्टी (heap property) का उल्लंघन होता है, तो नए जोड़े गए आइटम को उसके पेरेंट के साथ बार-बार स्वैप करके सही स्थान पर लाया जाता है:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # प्रारंभिक हीप
heap.append(6)                        # मान 6 वाले नए तत्व को जोड़ें

# ऊपर की ओर जाएं और हीप प्रॉपर्टी को सुधारें
node = len(heap) - 1                  # वर्तमान नोड का इंडेक्स
while node > 1:                       # जब तक हम रूट तक नहीं पहुंच जाते
    parent = node // 2                # पेरेंट नोड का इंडेक्स प्राप्त करें
    if heap[node] > heap[parent]:     # अगर हीप की संरचना सही नहीं है
        heap[node], heap[parent] = heap[parent], heap[node]
    else:                             # अगर संरचना सही है
        break                         # तो ऊपर वाले भी सही होंगे => रोक दें
    node //= 2                        # पेरेंट नोड पर जाएं

Delete the Root Element of a Heap

हीप से रूट एलिमेंट हटाने के लिए, इसे पहले एरे के आखिरी आइटम से बदल दिया जाता है और फिर (मैक्स-हीप (max-heap) का उदाहरण लेते हुए) उस नोड को उसकी सही जगह पर लाने के लिए उसे बार-बार उसके सबसे बड़े चाइल्ड के साथ स्वैप किया जाता है:

heap = [None, 8, 5, 7, 1, 1, 6, 3, 1] # प्रारंभिक हीप
heap[1], heap[-1] = heap[-1], heap[1] # रूट को आखिरी एलिमेंट से स्वैप करें
heap.pop()                            # आखिरी एलिमेंट हटाएं (जो पहले रूट था)

# नीचे की ओर जाएं और हीप प्रॉपर्टी को सुधारें
node = 1                              # वर्तमान नोड का इंडेक्स
while node < len(heap):               # जब तक हम अंत तक नहीं पहुंच जाते
    left = heap[2 * node] if 2 * node < len(heap) else float('-inf')
    right = heap[2 * node + 1] if 2 * node + 1 < len(heap) else float('-inf')
    
    # अगर हीप प्रॉपर्टी का उल्लंघन नहीं हुआ है => यहीं रुकें
    if heap[node] >= left and heap[node] >= right:
        break
    
    # यदि left > right => हमें बाएं दिशा में स्वैप करना चाहिए
    if left > right:
        heap[2 * node], heap[node] = heap[node], heap[2 * node]
        node = 2 * node
    else:
        heap[2 * node + 1], heap[node] = heap[node], heap[2 * node + 1]
        node = 2 * node + 1

Challenge: Fix the Heap

मान लीजिए कि हमारे पास n संख्याओं वाला एक मिन-हीप (min-heap) है, जहां पहले के n-1 संख्ये मिन-हीप प्रॉपर्टी को संतुष्ट करते हैं, लेकिन nवें स्थान पर मौजूद संख्या इस प्रॉपर्टी का उल्लंघन कर सकती है। आपका काम है इस हीप को इस तरह से ठीक करना, ताकि सभी संख्याएं असल में मिन-हीप की शर्तों का पालन करें।

Input

इनपुट की पहली पंक्ति में एकल पूर्णांक n (1 ≤ n ≤ ) दिया गया है।

अगली पंक्ति में n रिक्त-से-पृथक संख्याएँ () दी गई हैं, जो हीप में मौजूद तत्वों के मान को दर्शाती हैं।

Output

कार्यक्रम को ठीक किए गए हीप को दर्शाने वाली n स्पेस-से-पृथक संख्याएँ प्रिंट करनी चाहिए।

Examples

इनपुट	आउटपुट
7 1 2 5 4 3 6 -3	-3 2 1 4 3 6 5
6 5 6 9 20 10 8	5 6 8 20 10 9

Explanation

उदाहरण 1

उदाहरण 2