17599번 - Bags 다국어

Your friend Bob is a garbage collector working in a factory. The factory manufactures various kinds of chemical substances, and the toxic waste they may produce must be collected with caution. Every piece of toxic waste has an identifier that represents its chemical composition. It is very dangerous to put two pieces of toxic waste with different identifiers into a garbage bag, since they might produce some chemical reactions that lead to explosion, fire, toxic smoke or other chemical hazards.

Today, Bob has to collect n very small pieces of toxic waste, and their identifiers are a₁, a₂, . . . , a_n, respectively. These pieces are small enough to fit in one garbage bag, but Bob might as well use more bags to avoid any potential hazard. Please write a program to help Bob to calculate the minimum number of garbage bags required to safely collect all n pieces of toxic waste.

The first line of the input contains one integer n where n is the number of pieces of toxic wastes. The second line of the input contains n positive integers a₁, . . . , a_n which are the identifiers associated with the corresponding pieces.

Output the answer in a line.

• 2 ≤ n ≤ 10⁵, and a₁, . . . , a_n are positive integers at most 10⁹.