25631번 - 마트료시카 합치기

문제

마트료시카는 속이 비어있는 인형이다. 성빈이는 $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$번째 마트료시카의 크기이다.

출력

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

제한

힌트