Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n ամբողջ թվերից բաղկացած զանգված, պարզի այդ զանգվածի առավել երկար աճող ենթահաջորդականությունը։ Եթե կան մի քանի հավասար երկարություն ունեցող ենթահաջորդականություններ, կարող եք ցուցադրել դրանցից որևէ մեկը։
Ենթահաջորդականությունը որոշվում է զանգվածից որոշ (հնարավոր է զրո) էլեմենտներ ջնջելով, առանց փոխելու մնացած էլեմենտների հերթականությունը։ Օրինակ, եթե զանգվածը a=[3,1,4,1,5,9,2,6,5] է, ապա [3,4,5,6]-ը a-ի ենթահաջորդականություն է, իսկ [3,1,1,2,5]-ը չէ, քանի որ այստեղ էլեմենտների սկզբնական հերթականությունը չի պահպանվում։
Մուտք
Մուտքիแรก տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000)։
Մուտքի երկրորդ տողում տրված են n ամբողջ թվեր a1,a2,…,an (1 ≤ ai ≤ 10^9), որոնք ներկայացնում են զանգվածի էլեմենտները։
Ելք
Ծրագիրը պետք է տպի զանգվածի առավել երկար աճող ենթահաջորդականության երկարությունը։
Օրինակներ
Մուտք
Ելք
8 1 3 2 4 5 2 6 5
5
6 10 9 2 5 3 7
3
Պարզաբանում
Առաջին օրինակում զանգվածի առավել երկար աճող ենթահաջորդականությունը [1,2,4,5,6]-ն է։
Երկրորդ օրինակում առավել երկար աճող ենթահաջորդականությունը [2,5,7]-ն է։