Mountain Watching

Interview

Time limit1sMemory limit128 MB

Summary
Given a sequence of heights, find the longest consecutive block that rises (non-strictly) then falls (non-strictly), allowing a block that only rises or only falls.
Level

Medium4 of 10

Topics
Array, Two pointers, Implementation, Greedy
Solved
No attempts yet

Problem

Bessie is gazing off toward the beautiful mountains in the distance and wonders: which one is the widest?

She takes NN height measurements HiH_i one after another along the horizon, from left to right.

A mountain is a consecutive block of measurements whose heights first only rise (staying the same is allowed) and then only fall (staying the same is allowed). For example, 2,3,3,5,4,4,12, 3, 3, 5, 4, 4, 1 is a mountain. A mountain on the edge of her field of view may only rise, or only fall.

The width of a mountain is the number of measurements it spans. Help Bessie find the widest mountain and report its width.

A typical horizon looks like this:

           *******                   *
          *********                 ***
          **********               *****
          ***********           *********               *
*      *****************       ***********             *** *
**    *******************     *************   * *     *******      *
**********************************************************************
?ddsssuussuussssssddddssddssssuuuuuuuuddddddssududssssuuudduddsssssuds
3211112333677777776543332111112344456765432111212111112343232111111211
aaaaa                     cccccccccccccccccccc eeeeeee    ggggggggg
  bbbbbbbbbbbbbbbbbbbbbbbbbbbb             ddddd ffffffffff  hhhhhhhhh

The mountains are labeled 'a', 'b', and so on; here mountain 'b' is the widest, with width 28.

Sometimes it is easiest to find a mountain's width once you know where its highest part is.

Constraints:

  • 1≤N≤100001 \le N \le 10000
  • 1≤Hi≤1091 \le H_i \le 10^9

Input

  • Line 1: a single integer NN.
  • Lines 2 to N+1N + 1: line i+1i + 1 contains a single integer HiH_i.

Output

  • A single line containing one integer: the width of the widest mountain.

Hint

Consider the measurements 3,2,3,5,4,1,63, 2, 3, 5, 4, 1, 6. The widest mountain is 2,3,5,4,12, 3, 5, 4, 1, so its width is 55. Other mountains include 3,23, 2 and 1,61, 6. Note that 3,2,33, 2, 3 is not a mountain, because it falls and then rises.

Examples1

  1. Example 1

    Input
    7
    3
    2
    3
    5
    4
    1
    6
    
    Expected output
    5