단체줄넘기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 학생이 바라보는 방향에 자신보다 작은 학생만 있도록 줄을 세울 때 참여할 수 있는 최대 학생 수를 구한다.

난이도: 보통10점 중 4점
유형: 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

$N$ 명의 학생들이 단체줄넘기를 하려고 한다. 단체줄넘기를 하기 위해서는 한 줄로 나란히 서야 하고, 학생들은 각자 줄을 잡은 양쪽 방향 중 한 곳을 바라보고 서야 한다.

학생들은 각자 바라보는 방향에 자신보다 키가 크거나 같은 사람이 있다면 점프할 타이밍을 놓쳐 줄에 걸릴 수 있다. 학생들은 최대한 많이 단체줄넘기를 뛰고 싶어 하기 때문에, 줄에 걸릴 수 있는 상황을 만들지 않으려고 한다. 즉 자신이 바라보는 방향에 자신보다 키가 작은 학생들만 앞에 오도록 줄을 서려고 한다.

학생들의 키를 알고 있을 때, 이 중 최대 몇 명의 학생이 단체줄넘기에 참여할 수 있을까? 줄을 돌리는 사람은 주어진 학생에 포함되지 않는다.

입력

첫째 줄에 학생의 수 $N$ 이 주어진다. $\left( 1\leq N\leq 1\\, 000 \right)$

둘째 줄에 학생들의 키를 나타내는 정수 $A\_i$ 가 공백으로 구분되어 주어진다. $\left( 1\leq A\_i\leq 1\\, 000 \right)$

출력

줄에 걸릴 수 있는 상황을 만들지 않도록 학생들을 적절히 배치했을 때, 단체줄넘기에 참여할 수 있는 최대 학생 수를 출력한다.

예제3

예제 1
입력
```
5
1 2 3 4 5
```
예상 출력
```
5
```
예제 2
입력
```
10
1 3 2 4 2 4 4 3 2 7
```
예상 출력
```
8
```
예제 3
입력
```
5
10 10 10 10 10
```
예상 출력
```
2
```