Напиши програм који одређује најдужи строго растући подниз (не обавезно узастопних елемената) унутар датог низа.

Улаз

Са стандардног улаза се учитава број елемената низа \(n\) (\(1 \leq n \leq 50000\)), а затим елементи низа (цели бројеви, сваки у посебном реду).

Излаз

На стандардни излаз исписати дужину најдужег растућег подниза.

Пример

Улаз

10
3
2
6
9
5
4
3
7
2
8

Излаз

4

Објашњење

Један растући подниз дужине 4 је 2 6 7 8.