Heapify द्वारा किए गए स्वैप की संख्या

शुरुआत में एक खाली heap दिया गया है, जिसमें आपको q क्वेरीज़ करनी होंगी। ये क्वेरीज़ दो प्रकार की होती हैं:

1. add x – यह ऑपरेशन x को heap में जोड़ता है

2. pop – यह ऑपरेशन heap के रूट (root) को हटा देता है

प्रत्येक क्वेरी के लिए, आपको स्वैप की संख्या को प्रिंट करना है, जो heap को max-heap की शर्तें पूरी करने के लिए पुनर्संगठित (restructure) करने में लगती है।

pop ऑपरेशन के मामले में, रूट और अंतिम एलिमेंट (element) की अदला-बदली को भी एक स्वैप माना जाता है।

Input

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

इसके बाद की अगली q पंक्तियों में क्वेरीज़ दी गई हैं – हर पंक्ति में एक क्वेरी। गारंटी है कि सभी add क्वेरीज़ के लिए x का मान के परिमाण (absolute value) से अधिक नहीं होगा।

Output

प्रत्येक क्वेरी के लिए स्वैप की संख्या, प्रत्येक को एक नई पंक्ति पर छापें।

Examples