마트료시카 합치기

면접 대비

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

요약

빈 인형을 더 큰 빈 인형 안에 넣어 합칠 때, 남는 인형의 최소 개수를 구합니다.

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

문제

마트료시카는 속이 비어 있는 인형이다. 성빈이는 $N$ 개의 마트료시카를 가지고 있다. $i$ 번째 마트료시카의 크기는 $a_i$ 이고, 모든 마트료시카의 속은 비어 있다.

성빈이는 남아 있는 마트료시카 중에서 $i$ 번째와 $j$ 번째( $i \neq j$ ) 마트료시카를 고른 뒤, $i$ 번째 마트료시카를 $j$ 번째 마트료시카 속에 넣을 수 있다. 이때 $j$ 번째 마트료시카의 속이 비어 있어야 하고, $j$ 번째 마트료시카가 $i$ 번째 마트료시카보다 커야 한다. 합치면 남아 있는 마트료시카의 개수가 하나 줄어든다.

성빈이는 마트료시카를 최대한 합쳐서 정리하려고 한다. 성빈이가 마트료시카를 잘 합친다면 남아 있는 마트료시카의 최소 개수는 얼마인가?

입력

첫째 줄에 마트료시카의 개수 $N$ ( $1 \le N \le 1\ 000$ )이 주어진다.

둘째 줄에 정수 $a_1, a_2, ..., a_N$ ( $1 \le a_i \le 10^9$ )이 주어진다. $a_i$ 는 $i$ 번째 마트료시카의 크기이다.

출력

남아 있는 마트료시카의 최소 개수를 출력한다.

예제3

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