증가하는 부분수열 만들기

사진작가 동석은 사진을 찍기 위해 N명의 모델을 한 줄로 배열하고 있습니다 (1 ≤ N ≤ 50). 순서대로 i번째 모델의 키는 a(i)이며, 동석은 모델의 줄이 키에 따라 증가하면서 모델의 부분집합이 많으면 매력적인 사진이 될 것이라고 생각합니다.

구체적으로 다시 설명하자면, 부분수열은 모델 수열에서의 원소 집합 a(i1),a(i2),…,a(ik) , 일련의 지수에 있는 i1< i2< … < ik. 부분집합이 증가한다고 말하는 것은 a(i1) ≤ a(i2) ≤ … ≤ a(ik)입니다.

동석은 그의 모델 정렬에 증가하는 부분수열이 있기를 원합니다. 이를 달성하기 위해, 그는 처음에 임의의 부분수열을 선택하고 그 부분수열의 원소를 뒤집을 수 있습니다.

예를 들어, 우리가 아래의 배열을 가지고 있다면

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)…a(N)을 포함하며, 각각이 범위 1…50의 정수입니다.

최대 한 번의 부분수열의 내용을 뒤집어 가장 긴 증가하는 부분수열을 이룰 수 있는 요소의 수를 출력합니다.