32255번 - 지그재그 히스토그램 나누기

문제

너비가 1ドル$이고 높이가 $h_1,ドル $\cdots,ドル $h_N$인 $N$개의 직사각형을 순서대로 이어붙여 만든 히스토그램이 주어진다.

히스토그램을 밑변과 수직하게 잘라 몇 개의 조각으로 나누려고 한다. 만들어진 각 조각의 너비는 모두 양의 정수여야 한다. 또한 조각들을 순서대로 나열했을 때 각 조각에 완전히 포함되는 가장 넓이가 큰 직사각형의 넓이 값이 지그재그가 되어야 한다. 이러한 조건을 만족하며 나누어진 조각의 수를 최대화하려 한다.

엄밀히 말해, 당신은 다음과 같은 일을 하는 프로그램을 작성해야 한다.

길이 $n$의 수열 $[a_{1},\cdots ,a_{n}]$이 지그재그 수열이라는 것은 다음 두 조건 중 하나 이상을 만족하는 것이다.

• 모든 1ドル\leq i<n$에 대해, $i$가 짝수이면 $a_{i}\leq a_{i+1}$이고 $i$가 홀수이면 $a_{i}\geq a_{i+1}$
• 모든 1ドル\leq i<n$에 대해, $i$가 짝수이면 $a_{i}\geq a_{i+1}$이고 $i$가 홀수이면 $a_{i}\leq a_{i+1}$

히스토그램을 이용해 특정 조건을 만족하는 수열을 다른 수열로 바꿀 수 있다.

• 바꿀 수열은 길이가 $(k+1)$이고 $a_{1}=0,ドル $a_{k+1}=N$을 만족하는 강증가 수열 $[a_{1},a_{2},\cdots ,a_{k+1}]$이다.
• 바꾸고 난 후의 수열은 길이가 $k$이며, $[b_{1},b_{2},\cdots ,b_{k}]$로 표기하자.
• 모든 1ドル\leq i\leq k$에 대해, $b_{i}$는 $(a_{i}+1)$번째 직사각형부터 $a_{i+1}$번째 직사각형까지를 순서대로 이어 붙여 만든 히스토그램에서 넓이가 가장 큰 직사각형의 넓이이다.

당신은 위 작업의 조건을 만족하는 가능한 모든 수열 $[a_{1},a_{2},\cdots ,a_{k+1}]$에 대해, 작업을 시행하여 얻어지는 수열 $[b_{1},b_{2},\cdots ,b_{k}]$ 중 가장 길이가 긴 지그재그 수열의 길이를 구해야 한다.

입력

첫째 줄에 양의 정수 $N$이 주어진다. (1ドル\le N\le 500,円 000$)

둘째 줄에 $N$개의 양의 정수 $h_1,ドル $\cdots,ドル $h_N$이 공백을 사이에 두고 주어진다. (1ドル\le h_{i}\le 10^{9}$)

출력

첫째 줄에 문제의 정답을 출력한다.

제한

힌트