Recursive Segment Tree

आपको n एलिमेंट्स की एक array दी गई है। आपका कार्य है कि एक segment tree को पुनरावृत्ति (recursively) के जरिए बनाना और इस ट्रि में प्रत्येक node का मान निकालना। प्रत्येक node का मान उस node से जुड़े उप-array (subarray) का योग दर्शाता है।

इनपुट

इनपुट की पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 100000) आता है, जो array में मौजूद तत्वों की संख्या को दर्शाता है।

दूसरी पंक्ति में n स्पेस से अलग किए गए पूर्णांक () आते हैं, जो array के एलिमेंट्स को प्रदर्शित करते हैं।

आउटपुट

सभी nodes के मानों सहित segment tree को प्रिंट करें। segment tree की प्रत्येक लेवल एक नई पंक्ति में स्पेस से विभाजित करके दिखाई जानी चाहिए।

उदाहरण