Description

若一个序列满足$a$$1$$<$$a$$2$$<$…$<$$a$$n$，则该序列是有序$（$上升$）$的。

设给定数字序列$($$a$$1$,$a$$2$,…,$a$$n$$)$的子序列为任意序列$($$a$$i$$1$,$a$$i$$2$,…,$a$$i$$k$$)$，其中$1$$≤$$i$$1$$<$$i$$2$$<$…$<$$i$$k$$≤$$n$，例如序列$($$1$,$7$,$3$,$5$,$9$,$4$,$8$$)$有上升子序列如$($$1$,$7$$)$、$($$3$,$4$,$8$$)$和其他子序列。

所有最长的上升子序列的长度都是$4$，例如$($$1$,$3$,$5$,$8$$)$。

当给定数字序列时，找到其最长上升子序列的长度。

Format

Input

第$1$行包含序列的长度$n$$（$$1$$≤$$n$$≤$$1$$0$$0$$0$$）$；第$2$行包含序列的$n$个元素，每个元素都为$0$～$1$$0$$0$$0$$0$的整数。

Output

输出给定序列的最长上升子序列的长度。

Samples

7
1 7 3 5 9 4 8

4