가장 넓은 산 찾기

면접 대비

시간 제한1초메모리 제한128 MB

요약

높이 수열이 주어질 때, 증가하다가 감소하는(각 구간에서 같은 값 허용) 가장 긴 연속 구간의 길이를 구한다. 한쪽으로만 증가하거나 감소하는 구간도 산으로 인정한다.

난이도: 보통10점 중 4점
유형: 배열, 투 포인터, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

Bessie가 멀리 있는 아름다운 산들을 바라보다가 문득 궁금해졌습니다. 어떤 산이 가장 넓을까요?

Bessie는 지평선을 따라 왼쪽에서 오른쪽으로 차례대로 높이 $N$ 개를 측정했습니다. $i$ 번째 측정값을 $H_i$ 라고 합니다.

산이란, 높이가 먼저 계속 올라가기만 하다가(같은 값이 이어져도 됩니다) 그다음 계속 내려가기만 하는(같은 값이 이어져도 됩니다) 연속된 측정값 구간을 말합니다. 예를 들어 $2, 3, 3, 5, 4, 4, 1$ 은 하나의 산입니다. 시야의 가장자리에 있는 산은 올라가기만 하거나 내려가기만 할 수도 있습니다.

산의 너비는 그 산이 포함하는 측정값의 개수입니다. Bessie가 가장 넓은 산을 찾아 그 너비를 구하도록 도와주세요.

전형적인 지평선의 모습은 다음과 같습니다.

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

산에는 'a', 'b'처럼 이름이 붙어 있으며, 여기서는 산 'b'가 너비 28로 가장 넓습니다.

산의 가장 높은 부분이 어디인지 알면 그 산의 너비를 구하기 쉬운 경우가 많습니다.

제약 조건:

$1 \le N \le 10000$
$1 \le H_i \le 10^9$

입력

첫째 줄: 정수 $N$ 하나.
둘째 줄부터 $N + 1$ 째 줄까지: $i + 1$ 째 줄에 정수 $H_i$ 하나가 주어집니다.

출력

가장 넓은 산의 너비를 나타내는 정수 하나를 한 줄에 출력합니다.

힌트

측정값이 $3, 2, 3, 5, 4, 1, 6$ 이라고 합시다. 가장 넓은 산은 $2, 3, 5, 4, 1$ 이며 너비는 $5$ 입니다. 다른 산으로는 $3, 2$ 와 $1, 6$ 이 있습니다. $3, 2, 3$ 은 먼저 내려갔다가 다시 올라가므로 산이 아닙니다.

예제1

예제 1
입력
```
7
3
2
3
5
4
1
6
```
예상 출력
```
5
```