minict26

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

kid2201 có n hộp lập phương trống, hộp thứ i có kích thước là \(a_i\).

kid2201 có thể bỏ hộp thứ i vào trong hộp thứ j nếu như:

  • hộp thứ i chưa được bỏ vào bất kì hộp nào
  • hộp thứ j chưa chứa bất kì hộp nào bên trong
  • hộp thứ i nhỏ hơn hộp thứ j (\(a_i < a_j\))

kid2201 là một học sinh chuyên về thuật toán, muốn bỏ các hộp vào nhau sao cho số lượng hộp có thể nhìn thấy là ít nhất có thể.

Input

  • Dòng đầu tiên là số nguyên \(n\) \((1\le n\le 100000)\) - số lượng hộp lập phương
  • Dòng thứ hai gồm n số nguyên \(a_1, a_2, ..., a_n\) (\(1\le a_i\le 10^9\)).

Output

  • In ra số lượng hộp tối thiểu có thể nhìn thấy sao khi sắp xếp các hộp vào nhau.

Example

Test 1

Input
3
1 2 3
Output
1
Note

Trong test 1, hộp thứ 1 bỏ vào trong hộp thứ 2, hộp 2 bỏ vào trong hộp 3.

Test 2

Input
4
4 3 4 2
Output
2
Note

Trong test 2, hộp 2 bỏ vào hộp 3, hộp 4 bỏ vào hộp thứ 1.


Bình luận


  • 8
    kid2201 7:28 p.m. 1 Tháng 12, 2020

    hihihi justys