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