सबसे लंबी बढ़ती उपक्रम खोजें
आपको एक ऐसे ऐरे (array) की जानकारी दी गई है जिसमें
n पूर्णांक (integers) हैं। आपका काम इस ऐरे की सबसे लंबी बढ़ती उपक्रम (Longest Increasing Subsequence) खोजना है। यदि ऐसी कई उपक्रमें मौजूद हों, तो आप इनमें से कोई भी एक निकाल सकते हैं।ऐरे की किसी उपक्रम को, ऐरे के क्रम को बदले बिना, कुछ (या शून्य) तत्त्वों को हटाकर प्राप्त किया जाता है। उदाहरण के लिए, यदि ऐरे का मान है, तो ऐरे की एक उपक्रम है, लेकिन उपक्रम नहीं है क्योंकि इसमें तत्त्वों का क्रम वही नहीं रहता।
💡
किसी ऐरे की बढ़ती उपक्रम वह होती है जिसमें उसके सभी तत्त्व आरोही क्रम में हों। उदाहरण के लिए, यदि ऐरे का मान है, तो इसकी एक बढ़ती उपक्रम है, लेकिन बढ़ती उपक्रम नहीं है क्योंकि तत्त्व बढ़ते क्रम में व्यवस्थित नहीं हैं।
इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n (1 ≤ n ≤ 100 000) होता है, जो ऐरे की लंबाई दर्शाता है।दूसरी पंक्ति में
n अंतरालों से अलग किए गए पूर्णांक होते हैं (जहाँ ), जो ऐरे के तत्त्वों का प्रतिनिधित्व करते हैं।आउटपुट
आउटपुट की पहली पंक्ति में एक पूर्णांक
k छपना चाहिए, जो उस सबसे लंबी बढ़ती उपक्रम की लंबाई को दर्शाता है।आउटपुट की दूसरी पंक्ति में
k अंतरालों से अलग किए गए पूर्णांक होने चाहिए, जो उस सबसे लंबी बढ़ती उपक्रम का निरूपण करते हैं। यदि कई सही जवाब संभव हों, तो आप किसी भी एक को प्रदर्शित कर सकते हैं।Examples
Input | Output |
8
1 3 2 4 5 2 6 5 | 5
1 2 4 5 6 |
6
10 9 2 5 3 7 | 3
2 5 7 |
Note
दूसरे उदाहरण में, उपक्रम भी लंबाई 3 की एक मान्य बढ़ती उपक्रम है।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB