Երկարագույն աճող ենթահաջորդականություն 1

Ձեզ խնդրում են գրել ծրագիր, որը ստանալով n ամբողջ թվերից բաղկացած զանգված, պարզի այդ զանգվածի առավել երկար աճող ենթահաջորդականությունը։ Եթե կան մի քանի հավասար երկարություն ունեցող ենթահաջորդականություններ, կարող եք ցուցադրել դրանցից որևէ մեկը։

Ենթահաջորդականությունը որոշվում է զանգվածից որոշ (հնարավոր է զրո) էլեմենտներ ջնջելով, առանց փոխելու մնացած էլեմենտների հերթականությունը։ Օրինակ, եթե զանգվածը 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]-ը aa-ի ենթահաջորդականություն է, իսկ [3,1,1,2,5][3, 1, 1, 2, 5]-ը չէ, քանի որ այստեղ էլեմենտների սկզբնական հերթականությունը չի պահպանվում։

Մուտք

Մուտքիแรก տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000)։

Մուտքի երկրորդ տողում տրված են n ամբողջ թվեր a1,a2,…,ana_1, a_2, \dots, a_n (1 ≤ aia_i ≤ 10^9), որոնք ներկայացնում են զանգվածի էլեմենտները։

Ելք

Ծրագիրը պետք է տպի զանգվածի առավել երկար աճող ենթահաջորդականության երկարությունը։

Օրինակներ

Մուտք

Ելք

8
1 3 2 4 5 2 6 5

5

6
10 9 2 5 3 7

3

Պարզաբանում

  1. Առաջին օրինակում զանգվածի առավել երկար աճող ենթահաջորդականությունը [1,2,4,5,6][1, 2, 4, 5, 6]-ն է։

  2. Երկրորդ օրինակում առավել երկար աճող ենթահաջորդականությունը [2,5,7][2, 5, 7]-ն է։

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB