#6420. 浇灌土地

浇灌土地

背景

wsh 请了一周假,来到了乡下放松。他每天非常无聊,于是他想找一些事情来做。

题目描述

wsh 需要每天给花园浇水。花园是一个 1×n1 \times n 的矩形(由 11 行,nn 列/块横截面为正方形的土地组成),每块地都有一定的高度。他会选择从某一个地方开始浇水,如果与其相邻的土地高度不高于这块地的高度,水就可以流过去,反之流不过去。请问他一次最多可以浇灌多少块地?

如图,当纵截面高度为 4,2,3,3,24,2,3,3,2 时,如果我们在任意高度为 33 的土地上开始灌溉,水将流过除 44 以外的所有区域。

输入格式

第一行,一个正整数 nn,表示花园的列数。

第二行,nn 个正整数,表示每块地的高度 hih_i

输出格式

一行一个正整数,表示 wsh 可一次性灌溉的土地数量。

Samples

5
1 2 1 2 1
3
10
1 2 1 1 1 3 3 4 3 2
8

【样例解释】

样例 11

从任意一个 22 处开始流,左右均可流向 11,共流过 1+1+1=31+1+1=3 块土地。

样例 22

44 处开始流,向左可流至 22 的右边的 11,向右可流至 22,共流过 5+2+1=85+2+1=8 块土地。

【数据范围与约定】

本题采用 Subtask 捆绑测试。

对于 30%30\% 的数据,1n100,1hi10001 \le n \le 100,1 \le h_i \le 1000

对于 60%60\% 的数据,1n5000,1hi1041 \le n \le 5000,1 \le h_i \le 10^4

对于 100%100\% 的数据,1n5×105,1hi1061 \le n \le 5 \times 10^5,1 \le h_i \le 10^6

【说明/提示】

本题数据范围较大,请使用较快的读入方式。