暂无测试数据。

啊哈哈哈哈哈，周末来咯，啊哈哈哈哈哈哈哈。这解谜，多是一件美事啊。

作为解谜爱好者，蒜头君约上自己的好友，一起去玩密室逃脱，解谜大师蒜头君很快来到了最后一关。

这时，蒜头君遇到了一个大难题。

已知有一个序列，长度为 $n$，第 $i(1\leq i\leq n)$ 个数字为 $a_i(1\leq a_i\leq n)$，蒜头君每次可以从序列的最左边或者最右边拿走一个数字并加入自己的序列。现在，需要蒜头君回答，他能够取到的最长的递增序列长度为多少。

对于序列 $a$，有 $1\leq a_i\leq n$，且 $a_i\neq a_j(i\neq j,1\leq i, j\leq n)$。例如 $2,1,3,4$ 是一个合法的序列 $a$。

输入格式

输入共两行。

第一行输入一个正整数 $n$，表示序列的长度。

第二行输入 $n$ 个正整数 $a_i$。

输出格式

输出一个正整数，表示答案。

数据范围

对于 $30\%$ 的数据，有 $1\leq n\leq 20$。

对于 $100\%$ 的数据，有 $1\leq n\leq 10^5$。

3
1 2 3

3

5
2 1 5 4 3

4