题目描述

在一处古老的遗迹中，宝藏猎人艾拉发现了一系列雕刻在石壁上的神秘数字。据说这些数字是开启通往隐藏宝藏的密室的钥匙。每个数字代表一个试炼的级别，艾拉需要从中找出一组单调递增的级别序列，这代表着逐渐增加的试炼难度。只有当艾拉能够按顺序完成这些逐步升级的试炼时，密室的大门才会打开。 你的任务是帮助宝藏猎人艾拉找到最长的递增试炼级别序列。这个序列将帮助她顺利通过试炼，最终获取宝藏。

输入格式

• 第一行，输入一个整数 ( n )，代表序列的长度，即石壁上的数字总数。
• 第二行，输入 ( n ) 个整数，代表石壁上的试炼级别。

输出格式

• 输出一个整数，表示艾拉可以按顺序完成的最长递增试炼级别序列的长度。

数据范围

• 对于 ( 30% ) 的数据，( $1 \leq n \leq 100$)。
• 对于 ( 100% ) 的数据，( $1 \leq n \leq 5000$ )。

示例

输入

6
1 2 4 1 3 4

输出

4

解释

艾拉可以选择试炼级别 1, 2, 3, 4