문제 설명
영동 포도축제에서 많은 관광객들의 참여를 위해 오르락 내리락이라는 게임을 기획하고자 한다. 이 게임의 규칙은 다음과 같다.
1. 여러 사람들이 한 줄로 선다.
2. 이 중 일부를 뽑아 오르락 내리락 순서를 만족하는 줄을 만든다. 오르락 내리락 순서란, 모든 사람들이 처음에 서 있던 순서를 지키며 한 줄로 서고, 사람들의 키가 점점 커지다가 다시 작아지는 순서를 의미한다.
예를 들어, 5명의 사람이 서 있고 각각의 키가 {120, 180, 160, 190, 130}이라고 할 때, {120, 180, 160, 130}의 사람들을 뽑으면 규칙에 맞지만, {120, 180, 160, 190}은 규칙에 맞지 않는다.
또한, 오르락 내리락 순서가 된다면 서 있는 모든 사람을 뽑아도 되고, 가장 키가 큰 사람이 맨 앞 혹은 맨 뒤에 서도 된다.
사람의 수(N)과 N명의 사람들의 키(Ai)를 입력하면, 오르락 내리락 순서를 만족하는 가장 긴 줄의 길이를 출력하는 프로그램을 작성해보자.
입력 설명
첫 번째 줄에 사람의 수(N)가 입력된다.
(단, N은 정수이며, 1 ≤ N ≤ 1,000의 범위를 갖는다.)
두 번째 줄에 N명의 키(Ai)가 공백으로 구분되어 입력된다.
(단, Ai는 정수이며, 100 ≤ Ai ≤ 200의 범위를 갖는다.)
출력 설명
N명의 사람들로 만들 수 있는 가장 긴 오르락 내리락 순서의 길이를 출력한다.