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

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

1. 数列中的每个数都要染上一个颜色。

2. 如果数列中的两个整数 A_i 和 A_j 被染成相同的颜色，那么必须满足 i < j 且 A_i < A_j。

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

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

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

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

样例 1 说明

在第一个样例中，如下染色方案仅需 2 种颜色：

• 使用红色给数列中的 2 和 3 染色（2 < 3）。
• 使用蓝色给数列中的 1, 4, 5 染色（1 < 4 < 5）。

样例 2 说明

为每个数字分配一种不同的颜色。

数据范围

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

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