지그재그 히스토그램 나누기

너비가 $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}$이다.

다음 방법으로 히스토그램을 다른 수열로 바꿀 수 있다.

• $a_1 = 0$, $a_{k+1} = N$을 만족하는 강증가 수열 $[a_1, a_2, \cdots, a_{k+1}]$을 고른다.
• 그러면 길이가 $k$인 수열 $[b_1, \cdots, b_k]$가 만들어진다.
• 각 $1 \leq i \leq k$에 대해 $b_i$는 $a_i+1$번째 직사각형부터 $a_{i+1}$번째 직사각형까지를 순서대로 이어 붙인 히스토그램에서 넓이가 가장 큰 직사각형의 넓이이다.

가능한 모든 수열 $[a_1, \cdots, a_{k+1}]$에 대해 얻어지는 수열 $[b_1, \cdots, b_k]$ 중 지그재그 수열인 것의 최대 길이를 구한다.

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

둘째 줄에 공백으로 구분된 양의 정수 $h_1$, $\cdots$, $h_N$이 주어진다. ($1 \le h_i \le 10^{9}$)

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