3875 - 高楼

题目描述

在一条笔直的大街上,从左向右依次有 N 栋高楼编号 1 \sim N,第 i 栋高楼的高度为 H_i 米。

A 是一名数学爱好者,他想要从这 N 栋楼中找出若干栋楼构成的区间,并满足以下条件。

  • 按照从左向右的顺序,可以选择任意一栋高楼(假设编号为 L_i)作为起点,选择任意一栋高楼(假设编号为 R_i)作为终点,构成一个连续的区间。

  • 编号在 [Li, Ri] 区间范围内所有高楼必须满足从左向右看,他们的高度单调不递增。即:按照从左向右看,该区间中任意两栋相邻楼的高度 H_jH_{j+1},满足 H_j \geq H_{j+1}L_i \leq j \lt R_i)。

请编程帮助小 A 计算出,所有满足上述条件的高楼区间中,拥有高楼数量最多的区间里有几栋高楼?

输入

第一行包含一个整数 N,表示高楼的数量。

第二行包含 N 个整数 H_1, H_2, \dots, H_N,分别表示从左向右看每栋高楼的高度(单位:米)。

输出

输出一个整数,表示满足题意的高楼区间中,拥有高楼数量最多的区间里有几栋高楼。

样例

输入

5
10 4 8 7 3

输出

3

输入

7
4 4 5 6 6 5 5

输出

4

输入

4
1 2 3 4

输出

1
说明

样例 1 说明

2 个区间满足题目的要求。

1 个区间为 [1, 2],其中楼的高度为 10 4

2 个区间为 [3, 5],其中楼的高度为 8 7 3

显然第 2 个区间中拥有高楼的数量最多,有 3 栋高楼。

数据范围

对于 25\% 的数据,满足 1 \leq N \leq 20

对于 100\% 的数据,满足 1 \leq N \leq 10^51 \leq H_i \leq 10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 入门


上一题 下一题