बॉक्स छिपाना
आपके पास
n बॉक्स हैं, जिन्हें आप एक-दूसरे के अंदर छिपाकर उनकी संख्या कम से कम दिखाना चाहते हैं। इस प्रक्रिया में कुछ नियमों का पालन करना आवश्यक है:- यदि एक बॉक्स दूसरे बड़े बॉक्स के अंदर रखना है, तो बड़ा बॉक्स छोटे बॉक्स से कम-से-कम दोगुना बड़ा होना चाहिए।
- किसी भी बॉक्स के अंदर केवल 1 बॉक्स रखा जा सकता है (कोई भी बॉक्स 2 या उससे ज़्यादा बॉक्सों को एक साथ नहीं रख सकता)।
अंत में दृश्यमान (Visible) बॉक्सों की संभवतः सबसे कम संख्या कितनी हो सकती है?
इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n (1 ≤ n ≤ ) होता है, जो बॉक्सों की संख्या दर्शाता है।अगली पंक्ति में
n स्पेस से अलग किए हुए पूर्णांक (1 ≤ ≤ ) दिए जाते हैं, जो प्रत्येक बॉक्स का आकार बताते हैं।आउटपुट
कार्यक्रम को बॉक्सों की दिखाई देने वाली न्यूनतम संभव संख्या प्रिंट करनी चाहिए।
Examples
Input | Output |
8
7 5 2 6 4 8 9 2 | 5 |
8
3 1 8 2 6 5 6 9 | 5 |
Explanation
- 7 5 2 6 4 8 9 2 → (2, 5) (2, 6) (7) (4, 8) (9)
- 3 1 8 2 6 5 6 9 → 1 2 3 5 6 6 8 9 → (1, 5) (2, 6) (3, 6) (8) (9)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB