最强小队 (team)

• 输入：team.in
• 输出：team.out
• 时间限制：1 s
• 内存限制：128 MB

题目描述

信息学训练营中共有 $n$ 名同学排成一列，第 $i$ 名同学的能力值为 $a_i$。

教练希望从这列同学中选出若干名同学组成一支小队。选出的同学必须保持原来的相对顺序。

一支小队被称为“强队”，当且仅当它满足下面的条件：

• 如果小队只有 $1$ 名或 $2$ 名同学，则一定是强队。
• 如果小队人数不少于 $3$，那么小队第一名同学和最后一名同学的能力值，都必须严格大于小队中间所有同学的能力值。

小队的人数越多，就认为这支小队越强。请你求出强队最多可以包含多少名同学。

输入格式

从文件 team.in 中读入数据。

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每名同学的能力值。

输出格式

输出到文件 team.out 中。

输出一个整数，表示强队的最大人数。

样例1输入

3
3 1 2

样例1输出

3

样例1解释

可以选择全部 $3$ 名同学，得到能力值序列 $[3,1,2]$。

其中第一名同学的能力值为 $3$，最后一名同学的能力值为 $2$，都严格大于中间同学的能力值 $1$，因此这是一支强队。

不存在人数超过 $3$ 的小队，因此答案为 $3$。

数据范围

对于所有数据，$1 \le n \le 100000$，$1 \le a_i \le 10^9$。每个测试点 $5$ 分。