问题
'이상한 극장'은 구조가 매우 독특하여, 모든 좌석이 앞뒤로 일렬로 연결되어 있다.
따라서 극장 좌석에 앉아 있는 사람은 자기 앞에 있는 좌석들 중에 자기보다 키가 큰 사람이 한 명이라도 있으면 영화를 제대로 볼 수 없다.
(단, 키가 같은 사람이 앞에 있는 것은 괜찮다)
'이상한' 극장의 극장주는 최대한 입장 수입을 얻기 위해 동시에 가능하면 가장 많은 관객들이 영화를 보기를 원한다.
그러나 표를 키 순서대로 팔수는 없기 때문에 극장주는 동시에 몇 명이 영화를 제대로 볼 수 있는지를 알고 싶어 한다.
즉, 사람들이 표를 예매할 때 적어낸 키를 바탕으로 적당히 몇몇 사람에게만 표를 팔면, 그 사람들은 영화를 제대로 볼 수 있다.
이때, 예매한 순서도 지켜야 한다. 예를 들어, 예매한 사람의 키가 5 2 4 1 7 이라면, 5 7을 선택하면 2명이서 영화를 제대로 볼 수 있고,
2 4 7을 선택하면 3명이서 영화를 제대로 볼 수 있다.
이와 같이 예매를 하면서 사람들이 적어 낸 키를 바탕으로
최대 몇 명이 영화를 제대로 볼 수 있는지를 알아내는 가장 효율적인 알고리즘을 설계하고 프로그램하시오.
输入
입력파일의 첫줄에 몇 사람의 키가 들어올지를 나타낸다. 최대 100,000명까지 들어올 수 있다.
둘째 줄부터 사람의 키가 들어온다. 사람의 키는 100,000이하의 음이 아닌 정수이다.
输出
제대로 영화를 볼 수 있도록 했을 때 가장 많이 볼 수 있는 사람의 수를 첫 번째 줄에 출력하고,
경우의 수가 몇 가지나 되는지 구하여 987654313으로 나눈 나머지를 두 번째 줄에 출력한다.
示例
12
5 3 1 4 7 2 6 5 8 4 7 9
5
19
需要登录才能编写代码。