Training Site
Sideways banner

Cardboard Boxes

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

Avery is stacking cardboard boxes into a tower. They have N cardboard boxes that they can use, and each of them has some width. Specifically, Avery's ith box has a width of w_i. Avery is an award-winning architect, and therefore knows that putting a big thing on a small thing is structurally unsound. As such, they have decided that every box in the tower must be wider than the one above it. This rule does not apply to the box at the top of the tower (because there is no box above it).

As Avery's 'coding friend', they have asked you to to write a program that can tell them the maximum amount of boxes they can use in their tower.


The first line of input will contain a single integer N.

Each of the next N lines will contain a single integer, representing the width of one of Avery's cardboard boxes. More formally, among the next N lines, the ith will contain w_i.


You should output a single integer: The maximum number of boxes Avery can use in their tower.


  • 1 ≤ N ≤ 100{,}000
  • 1 ≤ w_i ≤ 10{,}000


  • For 30% of the marks, no two boxes have the same width
  • For an additional 30% of the marks, N ≤ 10
  • For full marks, no additional constraints apply

Sample Explanation

Avery can build a tower of height 3 by putting one of the width 3 boxes on top of the width 10 box, and the width 1 box on the top. Avery cannot fit the other width 3 box in anywhere without breaking their rule.

  • Sample Input 1


    Sample Output 1