Problem
नया खेल खेलते समय (गेंदबाजी और बिलियर्ड्स के कुछ संकर), N गेंदों का उपयोग किया जाता है, जिनकी संख्या 1 से N तक होती है। खेल की शुरुआत में, इन गेंदों को संख्यात्मक क्रम में एक पंक्ति में रखा जाना चाहिए। खेल के दौरान, उनका क्रम बदल सकता है।
अगले गेम के शुरू होने से पहले गेंदों को व्यवस्थित करने के लिए, निम्नलिखित डिवाइस का उपयोग किया जाता है। इस उपकरण में एक सिर होता है, जो गेंदों पर चलते हुए "चूस" सकता है और "थूकना" गुब्बारे। इस उपकरण का बेहतर विचार प्राप्त करने के लिए, एक वैक्यूम क्लीनर की कल्पना करें जो गेंदों को सोख सकता है, सही जगह पर जा सकता है, और वहां विपरीत दिशा में फूंक मारकर गेंदों को "थूक" सकता है।
जब एक गुब्बारे को चूसा जाता है, तो सभी गुब्बारे जो चूसे गए के दाईं ओर थे, बाईं ओर स्थानांतरित हो जाते हैं। "उगलना" गेंद किसी भी दो गेंदों के बीच हो सकती है (और पहली गेंद से पहले या आखिरी गेंद के बाद भी), फिर इन गेंदों के बीच थूकने वाली गेंद डाली जाती है, और डाली गई सभी गेंदों को दाईं ओर स्थानांतरित कर दिया जाता है ।
एक ही समय में डिवाइस में एक से अधिक गेंद को चूसा जा सकता है, और गेंद को बाहर थूकते समय, चूसी गई आखिरी गेंद को पहले थूक दिया जाता है, फिर अंत से पहले, और इसी तरह। (यानी डिवाइस स्टैक के सिद्धांत पर काम करता है)। गेंदों को एक-एक करके बाहर फेंका जाता है, अर्थात। आप केवल एक गेंद को थूक सकते हैं, बाकी को डिवाइस के अंदर छोड़ सकते हैं (इस मामले में, आप गेंदों को उसी या किसी अन्य स्थान पर "थूकना" जारी रख सकते हैं, या नई गेंदों को चूस सकते हैं)।
वर्णित संक्रियाओं में सर्वाधिक ऊर्जा-प्रधान गेंद को चूसने की संक्रिया है, इसलिए हम ऐसे संक्रियाओं की संख्या को न्यूनतम करना चाहते हैं।
एक प्रोग्राम लिखें, जो गेंदों की प्रारंभिक व्यवस्था को देखते हुए, गेंदों को संख्यात्मक क्रम में व्यवस्थित करने के लिए आवश्यक सक्शन की न्यूनतम संख्या निर्धारित करेगा।
इनपुट
इनपुट फ़ाइल में, संख्या N पहले दी गई है — गेंदों की संख्या (1≤N≤1000)। इसके बाद N संख्याएँ हैं जो गेंदों की संख्या उनके वर्तमान स्थान में बाएँ से दाएँ क्रम में देती हैं (प्रत्येक संख्या - 1 से N तक, और प्रत्येक संख्या क्रम में ठीक एक बार आती है)।
आउटपुट
एकल संख्या आउटपुट करें — गेंदों को उनकी संख्या के क्रम में व्यवस्थित करने के लिए आवश्यक गेंद चूसने की न्यूनतम संख्या।
नमूना परीक्षण पर टिप्पणियाँ
1. उदाहरण के लिए, आप गुब्बारे संख्या 2 को चूस सकते हैं और इसे पहले और तीसरे गुब्बारे के बीच थूक सकते हैं।
2.>आप ऐसा कुछ कर सकते हैं। सबसे पहले,
गुब्बारे नंबर 1 को चूसें, फिर – गेंद संख्या 2। फिर हम शुरुआत में जाते हैं और चौथी गेंद से पहले गेंद को थूक देते हैं (यह गेंद संख्या 2 होगी)। इसके बाद, गुब्बारे संख्या 3 को चूसें और इसे गुब्बारे 2 और 4 के बीच थूक दें। फिर शुरुआत में जाएँ और गुब्बारे संख्या 1 को वहाँ थूक दें। हालाँकि, इस उदाहरण में गुब्बारों का यह एकमात्र संभव क्रम नहीं है।
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स">
<शरीर>
| इनपुट |
आउटपुट |
<टीडी>
3
2 1 3
1 |
<टीडी>
4
4 3 2 1
3 |
टीम ओलंपियाड, मॉस्को टीम ओलंपियाड, ग्रेड 9-11, 2007, लीग ए, प्रॉब्लम एफ