오르락 내리락

정수로 이루어진 수열 $T$에서, 다음 조건을 만족하는 가장 긴 $P$의 길이를 구하는 프로그램을 작성하시오.

1. $P$는 $T$ 자신 또는 연속하는 부분으로 만들어진 수열이다.
2. $P$의 홀수 위치만 따서 만든 수열은 증가 수열이다.
3. $P$의 짝수 위치만 따서 만든 수열은 감소 수열이다.

조건 2, 3이 $P$의 길이가 꼭 짝수라는 것을 뜻하는 것이 아니라는 데 유의하시오.

예를 들어, $T = (10, 2, 9, 3, 8, 4, 7, 5, 6, 1)$일 때 $T$의 맨 처음과 마지막을 제거하여 $P = (2, 9, 3, 8, 4, 7, 5, 6)$을 만들면, 홀수 위치는 $(2, 3, 4, 5)$, 짝수 위치는 $(9, 8, 7, 6)$이 되어 모든 조건을 만족함을 알 수 있으며, 조건을 만족하면서 이보다 더 긴 경우는 찾을 수 없다.

만약, $T = (1, 10, 2, 9, 3, 8, 4, 7, 5, 6)$이라면, $T$ 자체로 이 조건을 만족함을 알 수 있다.

입력 형식

첫 줄에 수열 $T$의 크기를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 200\,000$)

그다음 줄에 수열 $T$의 구성을 나타내는 $N$ 개의 정수 $T_1, T_2, … , T_N$이 공백으로 구분되어 주어진다. ($1 \le T_i \le N;$ $T_i$는 서로 다름)

출력 형식

첫 줄에 조건을 만족하는 가장 긴 $P$의 길이를 출력한다.

예제 1

10
10 2 9 3 8 4 7 5 6 1

8

예제 2

4
1 2 3 4

3

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설