문제 번호 : 위성중계방송

문제 번호 : 위성중계방송

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 79  해결 문제 수: 21
[제출][채점상황][게시판][:]

문제 설명

올해는 베이징 올림픽이 개최되는 해이다. 베이징에서 열리고 있는 올림픽의 각종 경기가 위성을 통하여 실시간으로 중계되고 있다. 덕분에 우리는 안방에서 올림픽 경기를 관람할 수 있다. 중국에서 한국까지 좋은 화질의 방송을 전송하기 위해서는 중계 위성의 수가 많을수록 고화질로 영상을 전송할 수 있다고 한다. 하지만 위성들 사이로 방송신호를 중계할 때는 다음과 같은 규칙이 있다고 한다. [위성a]에서 [위성b]로 신호를 중계할 경우에는 [위성a]의 고도가 반드시 [위성b]의 고도보다 높아야 한다.

위의 예를 참고 하면, 중국에서 한국으로 방송신호를 중계할 경우 중국에서 [위성3]과 [위성5]를 통하여 한국으로는 방송신호를 중계할 수 있다. 하지만 [위성2]와 [위성4]를 거치는 경로를 통해서는 중계가 불가능하다. 그 이유는 [위성2]의 고도 보다 [위성4]의 고도가 높기 때문이다. 방송신호의 중계는 현재 위성보다 다음 위성의 고도가 낮아야만 가능하다는 규칙을 준수할 경우 한국으로 가장 고화질로 전송할 수 있는 경우는 [위성1] - [위성2] - [위성5]를 거치는 경우이다. 이 경우 3개의 위성을 이용할 수 있다. 위성의 수와 각 위성의 고도가 입력 값으로 주어질 때, 가장 좋은 화질로 전송하기 위해 이용할 수 있는 위성의 최대 수를 구하는 프로그램을 작성하시오.

입력

입력파일의 첫째 줄에 위성의 수 N이 주어진다. ( 3 <= N <= 1000 ) 다음 줄에는 N개의 높이 H가 공백으로 구분하여 입력된다. (0<H<=50,000)

출력

출력내용은 이용 가능한 가장 많은 위성 수를 첫째 줄에 출력한다.

입력예시

5
88 77 90 100 56

출력예시

3

도움말

[제출][채점상황]