एल्गोरिदम और डेटा संरचनाएँ

सबसे लंबी बढ़ती हुई उप अनुक्रम 1 (Longest Increasing Subsequence 1)

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

किसी array की उप अनुक्रम वह क्रम होता है जो array के कुछ (संभवतः शून्य) तत्त्वों को हटाकर प्राप्त किया जाता है, लेकिन शेष तत्त्वों का क्रम वही बना रहता है। उदाहरण के लिए, यदि array है a=[3,1,4,1,5,9,2,6,5]a = [3, 1, 4, 1, 5, 9, 2, 6, 5], तो [3,4,5,6][3, 4, 5, 6] इस array की एक उप अनुक्रम है। लेकिन [3,1,1,2,5][3, 1, 1, 2, 5] इसकी उप अनुक्रम नहीं है क्योंकि इसमें तत्त्वों का क्रम बरकरार नहीं रखा गया है।

इनपुट

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

इनपुट की दूसरी पंक्ति में n स्पेस-उपयोगी पूर्णांक a1,a2,…,ana_1, a_2, \dots, a_n होते हैं (1≤ai≤1091 \leq a_i \leq 10^9), जो array के तत्त्वों का प्रतिनिधित्व करते हैं।

आउटपुट

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

उदाहरण

Input

Output

8
1 3 2 4 5 2 6 5

5

6
10 9 2 5 3 7

3

व्याख्या

  1. पहले उदाहरण में, array की सबसे लंबी बढ़ती हुई उप अनुक्रम [1,2,4,5,6][1, 2, 4, 5, 6] है।

  2. दूसरे उदाहरण में, array की सबसे लंबी बढ़ती हुई उप अनुक्रम [2,5,7][2, 5, 7] है।

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB