가장 넓은 산

면접 대비

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

요약

높이 수열이 주어질 때, 감소하지 않다가 증가하지 않는 연속 구간 중 가장 긴 것의 길이를 구한다. 골짜기 지점은 양쪽 산에 모두 포함된다.

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

문제

베시(Bessie)는 지평선 너머로 펼쳐진 아름다운 산맥을 바라보다가 문득 궁금해졌습니다. 어떤 산이 가장 넓을까?

베시는 지평선을 따라 일정한 간격으로 $N$ 개 ( $1 \le N \le 100000$ )의 높이를 순서대로 측정했습니다. $i$ 번째 측정값을 $H_i$ ( $1 \le H_i \le 10^9$ )라고 합니다.

산은 값이 (같은 값을 포함하며) 증가하다가 이후 (같은 값을 포함하며) 감소하는, 연속한 측정값들의 구간으로 정의합니다. 예를 들어 $2, 3, 3, 5, 4, 4, 1$ 은 하나의 산입니다. 지평선의 양 끝에 있는 산은 증가만 하거나 감소만 할 수도 있습니다.

산의 너비는 그 산이 포함하는 측정값의 개수입니다. 가장 넓은 산의 너비를 구하세요.

다음은 지평선의 한 예시입니다.

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

각 산에는 'a', 'b' 등의 이름이 붙어 있습니다. 여기서는 산 b가 너비 $28$ 로 가장 넓습니다. 맨 왼쪽 산 a의 너비는 이 문제의 정의에 따라 $6$ 입니다.

입력

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

출력

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

힌트

서로 이웃한 두 산은 그 사이의 골짜기를 공유합니다. 즉 골짜기의 가장 낮은 지점에 있는 측정값은 왼쪽 산과 오른쪽 산 양쪽 모두에 속하며, 두 산의 너비에 각각 포함되어 셉니다.

예제3

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