AL09-4. Eng uzun o‘suvchi qism

Ketma-ketlikdan ba’zi elementlarni o‘chirib, qat’iy o‘suvchi qism ketma-ketlik hosil qilamiz. Uning eng katta uzunligi qancha?

Klassik O(n²) DP: dp[i] — i-elementda tugaydigan eng uzun qism. Katta testlar uchun O(n log n) kerak: har uzunlik uchun eng kichik «dum»ni saqlang va ikkilik qidiruvda yangilang.

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida n ta son.

Chiqish ma’lumotlari

Eng uzun o‘suvchi qism uzunligi.

Cheklovlar

1 ≤ n ≤ 10⁵, |aᵢ| ≤ 10⁹