Hội thi Olympic Khoa học viên tưởng là hội thi thường niên diễn ra giữa các trường Trung học cơ sở trên cả nước. Ngoài nội dung thi kiến thức học sinh giỏi, ban tổ chức còn có nội dung thi vận động dành cho các bạn học sinh. Năm nay, hội thi được tổ chức tại trường Ngôi Sao - thành phố XYZ. Ban tổ chức có một trò chơi vận động mới đó là cuộc thi xếp tháp dành cho các đội chơi.

Mỗi đội chơi được ban tổ chức cung cấp n khối hộp, và các đội phải xếp thành các tòa tháp thỏa mãn các yêu cầu sau:

• Mỗi đội nhận khối hộp đầu tiên và tạo tháp đầu tiên.
• Khi nhận được một khối hộp, các đội phải xếp luôn vào một tháp đã có hoặc tạo một tháp mới, sau đó mới được nhận khối hộp tiếp theo từ ban tổ chức.
• Các tòa tháp phải thỏa mãn điều kiện: khối hộp ở trên có thể tích không lớn hơn khối hộp ở ngay dưới nó.
• Không được chuyển khối hộp từ tòa tháp này sang tòa tháp khác.
• Mỗi đội cần phải xếp được càng ít tòa tháp càng tốt.

Nhiệm vụ của bạn là xác định số tòa tháp ít nhất có thể tạo thành.

Input

• Dòng đầu tiên chứa một số nguyên dương n là số lượng khối hộp.
• Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (ai <= 10^9) là thể tích của các khối hộp.

Output

• In ra một số nguyên duy nhất là số lượng tòa tháp ít nhất có thể tạo thành.

Ví dụ

Input

5
3 8 5 2 2

Output

2

Cho một dãy số nguyên dương A bao gồm các số được sắp xếp tăng dần, trong đó mỗi số đều chia hết cho ít nhất một trong ba số: 3, 5, hoặc 7.
Dãy A bắt đầu như sau: ~3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, \dots~

Yêu cầu: Cho số nguyên dương k, hãy tìm số thứ k trong dãy A.

Dữ liệu vào (Input):
Một dòng duy nhất chứa số nguyên dương k ~(1 \le k \le 2 \cdot 10^{15})~.

Kết quả ra (Output):
Một số nguyên duy nhất là số thứ k tìm được.

Ví dụ:

Cho dãy số nguyên dương ~A~ gồm ~N~ phần tử ~a_1, a_2, \dots, a_N~. Hãy tìm số nguyên dương ~P~ nhỏ nhất thỏa mãn đồng thời hai điều kiện:

1. ~P~ là một số chính phương (có dạng ~k^2~ với ~k~ nguyên dương).
2. ~P~ chia hết cho tất cả các phần tử trong dãy ~A~.

Yêu cầu: In ra số dư của ~P~ khi chia cho ~10^9 + 7~.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ~N~.
• Dòng tiếp theo chứa ~N~ số nguyên dương ~a_i~.

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả ~P \pmod{10^9+7}~.

Ví dụ: