Heapify द्वारा किए गए स्वैप की संख्या
शुरुआत में एक खाली heap दिया गया है, जिसमें आपको
q क्वेरीज़ करनी होंगी। ये क्वेरीज़ दो प्रकार की होती हैं:add x– यह ऑपरेशनxको heap में जोड़ता है
pop– यह ऑपरेशन heap के रूट (root) को हटा देता है
प्रत्येक क्वेरी के लिए, आपको स्वैप की संख्या को प्रिंट करना है, जो heap को max-heap की शर्तें पूरी करने के लिए पुनर्संगठित (restructure) करने में लगती है।
pop ऑपरेशन के मामले में, रूट और अंतिम एलिमेंट (element) की अदला-बदली को भी एक स्वैप माना जाता है।Input
इनपुट की पहली पंक्ति में एक इकलौता पूर्णांक
q (1 ≤ q ≤ ) दिया गया है।इसके बाद की अगली
q पंक्तियों में क्वेरीज़ दी गई हैं – हर पंक्ति में एक क्वेरी। गारंटी है कि सभी add क्वेरीज़ के लिए x का मान के परिमाण (absolute value) से अधिक नहीं होगा।Output
प्रत्येक क्वेरी के लिए स्वैप की संख्या, प्रत्येक को एक नई पंक्ति पर छापें।
Examples
Input | Output |
7
add 1
add 2
add -3
add 4
pop
add -2
pop | 0
1
0
2
2
0
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB