More Cow Photos timer 1s memory 1024MB

오늘 소들이 특히 장난기가 많다! FJ는 소들이 일렬로 서 있는 사진을 찍고 싶지만, 사진을 찍으려 하면 소들이 계속 자리를 바꾼다.

총 N마리의 소가 있고, 각 소는 1부터 N 사이의 정수 높이를 갖는다. FJ는 소들이 특정한 순서로 정렬된 상태에서 사진을 찍고 싶다. 구체적으로, 왼쪽부터 오른쪽으로 소들의 키가 h_1, \dots, h_K이라면, 이 키 배열은 다음 세 가지 조건을 만족해야 한다:

• 증가 후 감소하는 형태여야 한다.

  • h_1 \le \dots \le h_i \ge \dots \ge h_K

• 인접한 두 소의 키가 같아선 안 된다.

  • 모든 1 \le i < K에 대해 h_i \neq h_{i+1}

• 대칭이어야 한다.

  • 즉, i + j = K+1 이라면 h_i = h_j 이어야 한다.

  • 이는 배열이 좌우 대칭인 피라미드형 구조를 갖는다는 뜻이다.

FJ는 가능한 많은 소를 포함하는 사진을 찍고 싶다. 이를 위해, 그는 일부 소들을 제거하고, 남은 소들을 재배열할 수 있다. 사진에 포함될 수 있는 소의 최대 수를 알아보자.