মাহিব ‘দুষ্টু সাবসিক্যুয়েন্স’ খুব পছন্দ করে। সে তোমাকে একটি ক্যারেক্টারের অ্যারে ara[0,1,...,n-1]
দেবে যাতে n টি ইংরেজি বড় হাতের অক্ষর থাকবে। তোমাকে ঐ অ্যারের সবচেয়ে বড় দুষ্টু সাবসিক্যুয়েন্সের দৈর্ঘ্য প্রিন্ট করতে হবে।
এখন দুষ্টু সাবসিক্যুয়েন্সটা কি? একটি ক্যারেক্টারের অ্যারে ara[]
এর সাবসিক্যুয়েন্সকে তখনই দুষ্টু বলা হবে যখন এর ক্যারেক্টারগুলো প্রথমে আভিধানিকভাবে ছোট থেকে বড় হতে থাকে এবং পরে বড় থেকে ছোট হতে থাকে। যদি সিক্যুয়েন্সটির বাড়ন্ত অংশ না থাকে (শুধু কমা অংশ থাকে) তাহলেও সেটি সুন্দর। ঠিক একইভাবে যদি কমা অংশ না থাকে (শুধু বাড়ন্ত অংশ থাকে) তাহলেও সেটি সুন্দর।
ইনপুটের প্রথম লাইনে থাকবে মোট টেস্ট কেসের সংখ্যা t (0 < t < 101)। প্রতি টেস্ট কেসের প্রথম লাইনে n (3 ≤ n ≤ 500) এর মান ইনপুট দেয়া হবে, যা বোঝায় ara[]
এর দৈর্ঘ্য। এবং দ্বিতীয় লাইনে n টি ইংরেজি বড় হাতের অক্ষর ইনপুট দেয়া হবে, যেগুলো ara[]
এর উপাদান।
আউটপুটে প্রতি টেস্ট কেসের জন্য মাহিবের ইনপুট দেয়া অ্যারের সবচেয়ে বড় দুষ্টু সাবসিক্যুয়েন্সের দৈর্ঘ্যটি প্রিন্ট কর।
Input | Output |
---|---|
2 8 A K B J D E B A 6 H F C D B A | 6 5 |
১ম কেসে: সবচেয়ে বড় দুষ্টু সাবসিক্যুয়েন্সটি হলো {A, B, J, D, B, A} যার দৈর্ঘ্য ৬।
২য় কেসে: সবচেয়ে বড় দুষ্টু সাবসিক্যুয়েন্সটি হলো {H, F, C, B, A} যার দৈর্ঘ্য ৫।
Problem setter: Mashfiqur R. Khan (mashfiqur404)