시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 59 27 22 57.895%

문제

영선이는 과대 포장으로 유명한 남규 회사에서 아르바이트를 한다. 영선이는 여러 박스들을 여러겹으로 포장하는 업무를 맡았다. 박스를 포장할 때 규칙이 있는데, 일단 박스를 일렬로 주어진다. 그리고 앞에 있는 박스가 뒤에 있는 박스보다 작아야지만, 뒤에 있는 박스에 넣을 수 있다. 뒤에 있는 박스를 앞에 있는 박스에 넣을 순 없다.

박스의 크기가 앞에서부터 일렬로 주어졌을 때, 최대한 박스안에 박스를 넣어 과대 포장한 박스 개수를 구하시오.

입력

첫째 줄에는 박스의 개수 n이 주어진다.(1≤n≤5000)

다음 줄에는 박스의 크기 Ai가 앞에서부터 차례대로 주어진다.(1≤Ai≤100,000)

출력

최대한 박스안에 박스를 넣어 과대 포장을 할 때, 그 박스들의 개수를 구하시오.

예제 입력 1

4
1 2 3 4

예제 출력 1

4

예제 입력 2

4
4 3 3 1

예제 출력 2

1