지그재그 수열

어떤 수열에서 연속한 세 수를 볼 때 그 세 수가 단조증가하는 경우도 없고 단조감소하는 경우도 없으면, 이 수열을 지그재그 수열이라고 한다.

좀 더 정확하게는, 길이가 $N$인 수열 $A$가 $1 \le i \le N-2$인 모든 $i$에 대해 $A_i \le A_{i+1} \le A_{i+2}$도 만족하지 않고 $A_i \ge A_{i+1} \ge A_{i+2}$도 만족하지 않으면, $A$는 지그재그 수열이다.

길이가 $N$인 수열 $A$가 주어진다. $A$의 연속한 부분 수열 중 지그재그 수열인 것의 최대 길이를 구하여라.

길이가 $M$인 수열 $B$가 길이 $N$인 수열 $A$의 연속한 부분 수열이라는 말은, 어떤 $i$가 존재해서 $B_1 = A_i$, $B_2 = A_{i+1}$, ..., $B_M = A_{i+M-1}$이 성립한다는 뜻이다.

입력은 두 줄이다. 첫째 줄에 수열의 길이 $N$이 주어진다.

둘째 줄에 공백으로 구분된 정수 $N$개가 주어진다. $i$번째 수가 $A_i$이다.

$A$의 연속한 부분 수열 중 지그재그 수열인 것의 최대 길이를 출력한다.

• $3 \le N \le 5000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)