时间限制: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的情况，即连续上升或连续下降。