마트료시카 합치기

면접 대비

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

요약

크기가 주어진 N개의 마트료시카에서 작은 인형을 빈 큰 인형 속에 넣는 작업을 반복해 남길 수 있는 최소 개수를 구한다.

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

문제

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

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

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

입력

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

둘째 줄에 정수 $a\_1, a\_2, ... , a\_N$ 이 주어진다. $a\_i(1 \le a\_i \le 10^9)$ 는 $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
```