解题思路

设景点高度序列为 $a_1,a_2,\dots,a_n$，因为景点编号必须递增，所以本质上是在原序列中选一个子序列。

根据题意：

• 上山时，景点高度不能降低，即前半段是不下降子序列
• 下山时，景点高度不能变高，即后半段是不上升子序列

题目内容

暑期小明打算去爬山，他选择了一个景点最多的山，山上有很多值得一去的景点，每个景点都有一个编号，并且其海拔高度小明也已经知道。

小明希望这次爬山的计划是先往高处爬，再往低处去，沿途参观风景。

因此小明在选择景点的时候，在爬山过程中，参观的景点的高度不能降低，在下山的过程中，景点的高度不能变高，同时由于门票的限制，参观景点的编号必须越来越大。你能合理挑选景点，让小明参观更多的景点么?

输入描述

第一行一个整数$n$，表示景点的总数量，$1<=n<=100000$

第二行$n$个整数，从左到右景点编号依次是$1$到$n$，数字大小表示景点高度，任意数字大小范围是$[1,1000000000]$。

输出描述

一个整数，表示小明最多可以参观景点的数量。

样例1

输入

9
2 7 3 5 4 9 1 8 6

输出

6

说明

样例解释：参观2,3,4,9,8,6

样例2:

输入:

3

1 2 3

输出:

3

样例3:

输入:

3

3 2 1

输出:

3