마트료시카 인형

아담은 친구 마트료나에게서 마트료시카 인형(러시아 전통 인형)이 가득 담긴 상자를 받았다. 모든 인형은 밑바닥이 비어 있어서, 인형 하나는 자기보다 작은 인형 하나를 바로 안에 넣을 수 있다.

모든 인형은 모양은 같지만 크기가 서로 다르다. 인형 $i$는 높이를 나타내는 하나의 수 $h_i$로 표현된다. 인형 $i$는 $h_i < h_j$일 때에만 인형 $j$ 바로 안에 들어갈 수 있으며, 각 인형은 자기 바로 안에 최대 한 개의 인형만 담을 수 있다(그 안의 인형이 또 다른 인형을 담아 겹겹이 쌓인 형태가 될 수 있다).

아담은 인형들을 서로 겹쳐 넣어서 가장 바깥에 있는 인형(다른 어떤 인형에도 들어가 있지 않은 인형)의 개수를 최소로 만들고 싶다. 모든 인형의 높이가 주어질 때, 가능한 가장 바깥 인형의 최소 개수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 인형의 개수를 나타내는 정수 $N$ ($1 \le N \le 10^5$)이 적힌 줄로 시작한다. 그 다음 $N$개의 줄에는 각각 $i$번째 인형의 높이를 센티미터 단위로 나타내는 정수 $h_i$ ($1 \le h_i \le 10^9$)가 하나씩 주어진다. 입력의 끝은 $N = 0$인 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 인형들을 최적으로 겹쳐 넣었을 때 가장 바깥 인형의 최소 개수를 한 줄에 하나씩 출력한다.