Informatica Online Judge

  위성중계방송 [0230 / 00E6]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 168   Total Tried : 215


The Champion of this Problem (C++) : gs17100 - ms / 332byte
My Best Submission (C++) : N/A

[]

Background

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



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

Input

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

Output

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

IO Example

입력
5
88 77 90 100 56

출력
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]