题目内容

小Z有一段由 $n$ 个音符组成的旋律，第 $i$ 个音符的音高为 $a_i$。现在他想按照原有顺序选取尽可能多的音符，使得选取出的子序列的音高先非严格上升，后非严格下降。换句话说，存在一个位置 $k$，使得前半段 $a_{i_1} \le a_{i_2} \le \dots \le a_{i_k}$，后半段 $a_{i_k} \ge a_{i_{k+1}} \ge \dots \ge a_{i_m}$（$i_1 < i_2 < \dots < i_m$）。请你帮忙计算最多能选取的音符个数。

数据范围：$1 \le n \le 10^5$，$1 \le a_i \le 10^9$，且所有数值均为整数。

输入描述

第一行包含一个整数 n。 第二行包含 n 个整数，依次表示 $a_1, a_2, \dots, a_n$，相邻整数用空格分隔。

输出描述

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

样例1

输入

1
10

输出

1

说明

只有一个音符，无论山峰形状如何定义，都只能选取这一个音符，因此最多选取 1 个音符。

样例2

输入

4
7 7 7 7

输出

4

说明

所有音符的音高均为 $7$。可以选出全部 4 个音符构成子序列，前半段 $7 \le 7 \le 7$ 满足非严格上升，后半段 $7 \ge 7 \ge 7$ 满足非严格下降（高峰位置可以选在第 2 个或第 3 个音符），因此答案为 4。

样例3

输入

8
4 2 5 5 6 3 1 4

输出

6

说明

一种最优选取方案为子序列 $2, 5, 5, 6, 3, 1$。前半段 $2 \le 5 \le 5 \le 6$ 为非严格上升，后半段 $6 \ge 3 \ge 1$ 为非严格下降，共 6 个音符。可以验证不存在更长的合法子序列，故答案为 6。