'이상한 극장'은 구조가 매우 독특하여, 모든 좌석이 앞뒤로 일렬로 연결되어 있다.

따라서 극장 좌석에 앉아 있는 사람은 자기 앞에 있는 좌석들 중에 자기보다 키가 큰 사람이 한 명이라도 있으면 영화를 제대로 볼 수 없다.

(단, 키가 같은 사람이 앞에 있는 것은 괜찮다)

'이상한' 극장의 극장주는 최대한 입장 수입을 얻기 위해 동시에 가능하면 가장 많은 관객들이 영화를 보기를 원한다.

그러나 표를 키 순서대로 팔수는 없기 때문에 극장주는 동시에 몇 명이 영화를 제대로 볼 수 있는지를 알고 싶어 한다.

즉, 사람들이 표를 예매할 때 적어낸 키를 바탕으로 적당히 몇몇 사람에게만 표를 팔면, 그 사람들은 영화를 제대로 볼 수 있다.

이때, 예매한 순서도 지켜야 한다. 예를 들어, 예매한 사람의 키가 5 2 4 1 7 이라면, 5 7을 선택하면 2명이서 영화를 제대로 볼 수 있고,

2 4 7을 선택하면 3명이서 영화를 제대로 볼 수 있다.

이와 같이 예매를 하면서 사람들이 적어 낸 키를 바탕으로

최대 몇 명이 영화를 제대로 볼 수 있는지를 알아내는 가장 효율적인 알고리즘을 설계하고 프로그램하시오.

이상한극장2 timer 1s memory 128MB

이상한극장2 1s 128MB