Xếp hộp

Có \(N\) hộp giấy được đánh số từ \(1\) đến \(N\). Hộp \(i\) có kích thước \(a_i\).
Ta cần xếp các hộp này thành ít đống nhất theo quy tắc:

• Các hộp được xét lần lượt theo thứ tự từ trái qua phải (\(1, 2, \ldots, N\)); mỗi hộp hoặc được đặt vào một đống đã có, hoặc tạo thành một đống mới.

• Mỗi đống gồm các hộp lồng nhau: hộp kích thước bé hơn nằm trong hộp kích thước lớn hơn.

• Một hộp chỉ được đặt vào một đống nếu kích thước của nó nhỏ hơn hẳn kích thước hộp nhỏ nhất hiện có trong đống đó (hai hộp cùng kích thước không lồng được vào nhau).

Hãy tìm số đống ít nhất \(D\) có thể tạo ra.

Input

• Dòng đầu chứa số \(N\) (\(1 \le N \le 5000\)).

• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 60000\)), là kích thước các hộp.

Output

In ra số đống ít nhất \(D\).

Notes

Với \(a = (4, 2, 5, 1, 3)\): có thể xếp thành \(2\) đống \((4, 2, 1)\) và \((5, 3)\), nên \(D = 2\).