#1266. [经开区 ] 最广山脉

[经开区 ] 最广山脉

时间限制:1000ms  空间限制:256MB

题目描述

小美的爸爸特别爱好登山,在小美很小的时候就带着她爬大蜀山、紫蓬山。在小美上小学期间,他们一家还去过天柱山、黄山、华山等等很多名山。图图常听小美聊登山的趣闻,听得心里直痒痒。他常想,要是自己也在小美家,该有多好呀。图图也曾问过小美,她爸爸最想爬的是哪座山,她说可能是珠穆朗玛峰吧,但是太危险,真的太危险了,所以不曾去过。图图对于这些大山,虽身不能至,但心向往之。有时他会在纸上写下他知道的一些山峰的高度,然后他想,如果把这些高度写成一行,就会构成多个起伏多变的地形。当然,总有一些山峰,会连绵成一片广袤的山脉。现有n座山峰,假如第i座山峰的高度为a[i]。现在给出最广山脉的定义,在x到y的范围以内,有若干个数,分别表示若干座山峰的高度,如果存在k,满足:

a[x]<a[x+1]<...<a[k-1]<a[k]>…>a[y-2]>a[y-1]>a[y]

则从x到y构成了一片山脉,如果从x到y个数是符合条件的山脉中最多的,则称从x到y构成最广山脉。请你统计并输出图图写出的n座山峰里面的最广山脉的山峰数量。

输入格式

两行:第一行,一个正整数n,表示山峰数量;第二行,n个正整数,表示每座山峰的高度,单位是米。

输出格式

一行,一个正整数,是最广山脉山峰的数量。

样例

输入#1

7
260 1860 100 480 800 650 400

输出#1

5

解释#1

本样例有两处山脉,一处有三座山峰,高度分别是260、1860、100,另一处有五座山峰,高度分别是100,480,800,650,400。5>3,因此最广山脉是第二处,所以输出5。

数据范围/约定

对于60%的数据1<=n<=10000。

对于100%的数据1<=n<=1000000。

对于100%的数据,1<=a[i]<=8848。

提示

可能存在xk或yk的情况,即连续上升或连续下降。