문제

가은이는 사진을 찍기 위해 $N$명의 친구를 한 줄로 세우려고 한다 ($1 \le N \le 50$). $i$번째 친구의 키는 $a_i$이다. 가은이는 친구들의 키로 이루어진 부분 수열 중 증가하는 부분 수열의 길이가 길수록 사진이 아름답다고 생각한다.

부분 수열이란 원래 수열의 원소 일부를 선택하여 만든 수열 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$를 말하며, 이때 인덱스는 $i_1 < i_2 < \ldots < i_k$를 만족해야 한다. 이 부분 수열이 $a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k}$를 만족하면 증가하는 부분 수열이라고 한다.

가은이는 사진을 찍기 전에 임의의 부분 수열 하나를 골라 그 원소들의 순서를 뒤집을 수 있다.

예를 들어, 다음과 같은 수열이 있다고 하자.

1 6 2 3 4 3 5 3 4

여기서 표시된 부분 수열을 선택하여 뒤집으면:

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

다음과 같은 수열을 얻는다.

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

뒤집힌 부분 수열의 원소들은 원래 차지하던 인덱스 위치를 그대로 유지하며, 선택되지 않은 다른 원소들은 변하지 않음에 유의한다.

임의의 부분 수열을 최대 한 번 뒤집을 수 있을 때, 얻을 수 있는 증가하는 부분 수열의 최대 길이를 구하시오.

입력

첫째 줄에 친구의 수 $N$이 주어진다. ($1 \le N \le 50$) 이어서 $N$개의 줄에 걸쳐 각 친구의 키 $a_1, \dots, a_N$이 한 줄에 하나씩 정수로 주어진다. ($1 \le a_i \le 50$)

출력

부분 수열을 최대 한 번 뒤집어 얻을 수 있는 증가하는 부분 수열의 최대 길이를 출력한다.

예제 입력 1

9
1
2
3
9
5
6
8
7
4

예제 출력 1

9