गैर-घटते क्रम की अनिवार्यता
आपको
n इन्टीजर का एक array (ऐरे) दिया गया है, जिसे गैर-घटते क्रम (non-decreasing) में बनाने के लिए आप निम्न ऑपरेशन को शून्य या अधिक बार कर सकते हैं:किसी भी इंडेक्स
i (1 ≤ ) को चुनें और को किसी भी इन्टीजर से बदल दें।आपका लक्ष्य इस ऐरे को गैर-घटते क्रम में बनाने के लिए आवश्यक ऑपरेशनों की कुल संख्या को कम से कम रखना है।
💡
औपचारिक रूप से, अगर किसी array
a के लिए सभी i और j (जहाँ 1 ≤ i < j ≤ n) पर ≤ सत्य हो, तो वह array गैर-घटते क्रम में होता है।इनपुट
इनपुट की पहली पंक्ति में एकल इन्टीजर
n (1 ≤ n ≤ 100000) दिया जाता है, जो ऐरे की लंबाई को दर्शाता है।दूसरी पंक्ति में
n स्पेस से अलग किए गए इन्टीजर होते हैं (1 ≤ ≤ ).आउटपुट
प्रोग्राम को एकल इन्टीजर प्रिंट करना चाहिए — इस ऐरे को गैर-घटते क्रम में बनाने के लिए आवश्यक न्यूनतम ऑपरेशनों की संख्या।
उदाहरण
इनपुट | आउटपुट |
7
1 3 2 2 7 4 3 | 3 |
4
1 2 1 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB