अधिकतम योग के साथ सबसे लंबा बढ़ता हुआ उपक्रम

आपके पास n पूर्णांकों का एक ऐरे दिया गया है, और आपको इस ऐरे का सबसे लंबा बढ़ता हुआ उपक्रम (Longest Increasing Subsequence) खोजना है। अगर ऐसे उपक्रम एक से ज़्यादा हों, तो आप किसी भी एक को आउटपुट कर सकते हैं।

किसी ऐरे का उपक्रम (subsequence) बनाने के लिए, हम ऐरे से कुछ (हो सकता है कि कोई भी नहीं) तत्वों को हटाते हैं, लेकिन बचे हुए तत्वों का क्रम वही रखते हैं। उदाहरण के लिए, यदि ऐरे है, तो , का एक उपक्रम है, लेकिन उपक्रम नहीं है, क्योंकि इसमें तत्वों का क्रम बदल गया है।

इनपुट

इनपुट की पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 1000) होता है, जो ऐरे की लंबाई दर्शाता है।

इनपुट की दूसरी पंक्ति में n स्पेस से अलग किए गए पूर्णांक होते हैं (), जो ऐरे के तत्वों का प्रतिनिधित्व करते हैं।

आउटपुट

कार्यक्रम को अधिकतम योग वाले सबसे लंबे बढ़ते हुए उपक्रम का योग प्रिंट करना चाहिए।

व्याख्या

1. पहले उदाहरण में, अधिकतम योग वाला सबसे लंबा बढ़ता हुआ उपक्रम है।

2. दूसरे उदाहरण में, अधिकतम योग वाला सबसे लंबा बढ़ता हुआ उपक्रम है।