The Widest Mountain

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of heights, find the longest contiguous run that is non-decreasing then non-increasing; valleys are shared by both neighboring mountains.

Level: Medium4 of 10
Topics: Array, Implementation, Greedy, Two pointers
Solved: No attempts yet

Problem

Bessie was gazing into the distance at a beautiful mountain range along the horizon when she wondered to herself: which mountain is the widest?

She took $N$ ( $1 \le N \le 100000$ ) equally-spaced height measurements in order along the horizon. Let $H_i$ ( $1 \le H_i \le 10^9$ ) be the $i$ -th measurement.

A mountain is a consecutive sequence of measurements whose values first increase (or stay the same) and then decrease (or stay the same); for example, $2, 3, 3, 5, 4, 4, 1$ is one mountain. A mountain at the edge of the horizon may only increase or only decrease.

The width of a mountain is the number of measurements it contains. Find the width of the widest mountain.

Here is one example of a horizon:

           *******                   *
          *********                 ***
          **********               *****
          ***********           *********               *
*      *****************       ***********             *** *
**    *******************     *************   * *     *******      *
**********************************************************************
3211112333677777776543332111112344456765432111212111112343232111111211
aaaaaa                   ccccccccccccccccccccc eeeeeee    ggggggggg
  bbbbbbbbbbbbbbbbbbbbbbbbbbbb             ddddd ffffffffff  hhhhhhhhh

The mountains are labeled 'a', 'b', and so on. Here mountain b is the widest, with width $28$ . The leftmost mountain a has width $6$ for the purposes of this problem.

Input

Line 1: a single integer $N$ .
Lines 2 to $N+1$ : line $i+1$ contains a single integer $H_i$ .

Output

Line 1: a single integer, the width of the widest mountain.

Hint

Two neighboring mountains share the valley between them: the measurement at the bottom of a valley belongs to both the mountain on its left and the mountain on its right, so it is counted in the width of each.

Examples3

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