Farmer John은 소 $N$마리를 한 줄로 세워 촬영한다 ($1 \leq N \leq 50$). $i$번째 소의 키는 $a(i)$이며 키가 증가하는 부분 수열이 길면 사진이 아름답다고 생각한다.

부분 수열은 인덱스 $i_1 < i_2 < \ldots < i_k$에서 고른 $a(i_1), a(i_2), \ldots, a(i_k)$이다. $a(i_1) \leq a(i_2) \leq \ldots \leq 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$이다. 나머지 $N$줄은 $a(1) \ldots a(N)$이며 각 값은 $1 \ldots 50$ 범위의 정수이다.

출력

표준 출력에 쓴다.

최대 한 부분 수열을 뒤집은 뒤 가능한 최장 증가 부분 수열의 원소 수를 출력하라.

예제

입력 1

9
1
2
3
9
5
6
8
7
4

출력 1

9

문제 출제자: Lewin Gan