暂无测试数据。

有一个长度为 $n$ 的整数序列 $\{a_1,a_2,\cdots,a_n\}$，现在将其复制 $n$ 份，变成这样：

$$\displaystyle \{a_1,a_2,\cdots,a_n,\cdots,a_1,a_2,\cdots,a_n,\cdots,a_1,a_2,\cdots,a_n\} $$

然后现在需要你 从左到右 依次取出 一些元素组成一个子序列，满足序列内元素是稳定上升的。问这个序列最长长度是多少。

输入格式

第一行为一个整数 $n$。

第二行为整数序列 $a_1,a_2,\cdots,a_n$。$n$ 个整数用空格隔开，都不大于 $10^5$。

对于 $40\%$ 的数据满足 $n\le 3$。

对于 $60\%$ 的数据满足 $n\le 50$。

对于 $80\%$ 的数据满足 $n\le 10^3$。

对于 $100\%$ 的数据满足 $n\le 10^5$。

输出格式

只有一行，为要求序列的最长长度。

3
3 2 1

3

6
3 1 4 1 5 9

5