프로그램 명: dolls
제한시간: 1 초

[요약] 마트료시카 인형은 인형 안에 인형이 들어가있는 형태의 러시아의 인형입니다. 인형들의 크기가 주어졌을 때 총 몇 개의 마트료시카 인형을 만들 수 있는지 출력하세요

Adam just got a box full of Matryoshka dolls (Russian traditional) from his friend Matryona. When he opened the box, tons of dolls poured out of the box with a memo from her:

Hi Adam, I hope you enjoy these dolls. But sorry, I didn't have enough time to sort them out. You'll notice that each doll has a hollow hole at the bottom which allows it to contain a smaller doll inside. ...
Yours,
Matryona

Adam, who already has so many things in his showcase already, decides to assemble the dolls to reduce the number of outermost dolls. The dolls that Matryona sent have the same shape but different sizes. That is, doll i can be represented by a single number h i denoting its height. Doll i can fit inside another doll j if and only if hi < hj . Also, the dolls are designed such that each doll may contain at most one doll right inside it. While Adam is stacking his gigantic collection of Matryoshka dolls, can you write a program to compute the minimum number of outermost dolls so that he can figure out how much space he needs in his showcase?

입력

Each test case begins with a line with an integer N , 1 <= N <= 10^5 , denoting the number of Matryoshka dolls. This is followed by N lines, each with a single integer hi , 1 <= hi <= 10^9 , denoting the height of the ith doll in cm.

출력

Print out a single line that contains an integer representing the minimum number of outermost dolls that can be obtained by optimally stacking the given dolls.

입출력 예

입력

4
5
7
7
3

출력

2

입력

3
10
10
10

출력

3

입력

3
10
999999999
100000000

출력

1

출처:standford/2010/
요약:ladown21
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]