Longest Increasing Subsequence 2
Տրված է n ամբողջ թվերից կազմված զանգված. Ձեր խնդիրը կլինի գտնել զանգվածի ամենաերկար աճող ենթահաջորդականությունը: Եթե קיימում են մի քանի հնարավոր ամենաերկար աճող ենթահաջորդականություններ, կարող եք տպել դրանցից ցանկացածը:
Զանգվածի ենթահաջորդականություն կարելի է ստանալ՝ հեռացնելով որոշ (հնարավոր է նաև ոչ մեկ) տարրեր, առանց փոխելու մնացած տարրերի հաջորդականությունը: Օրինակ, եթե զանգվածը է, ապա -ը -ի ենթահաջորդականություն է, իսկ -ը ենթահաջորդականություն չէ, քանի որ սկզբնական տարրերի կարգը խախտվել է:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000), որը զանգվածի երկարությունն է:
Մուտքի երկրորդ տողում տրված են n ամբողջ թվեր (), որոնք կազմում են զանգվածի տարրերը:
Ելք
Ծրագիրը ելքում պետք է տպի զանգվածի ամենաերկար աճող ենթահաջորդականության երկարությունը:
Օրինակներ
Մուտք | Ելք |
|---|---|
8 1 3 2 4 5 2 6 5 | 5 |
6 10 9 2 5 3 7 | 3 |
Բացատրություն
Առաջին օրինակում զանգվածի ամենաերկար աճող ենթահաջորդականությունը է:
Երկրորդ օրինակում զանգվածի ամենաերկար աճող ենթահաջորդականությունը է:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB