当前没有测试数据。

题目描述

在一项数学研究中，研究员正在研究一个包含了 $N$ 个整数的数列 $A = A_1, A_2, …, A_N$。

他们希望对这些整数进行染色，使得满足以下条件：

• 数列中的每个数都要染上一个颜色。
• 如果数列中的两个整数 $A_i$ 和 $A_j$ 被染成相同的颜色，那么必须满足 $i < j$ 且 $A_i < A_j$。

研究员的目标是，使用最少的颜色数来完成这个染色任务。请你编程帮助他们计算出最受需要多少个颜色，才能完成这项染色任务？

输入格式

输入的第一行包含一个整数 $N$，表示数列中的整数个数。

接下来 $N$ 行，包含了 $N$ 个整数 $A_1, A_2, …, A_N$，表示数列的元素。

输出格式

输出一个整数，表示完成染色所需的最小颜色数。

样例 #1

输入

5
2 1 4 5 3

输出

2

数据范围

对于 $10\%$ 的数据，满足数列中的 $N$ 个数严格单调递增，或者严格单调递减。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$0 \le A_i \le 10^9$。