Dãy số đẹp theo số ước

Với mỗi số nguyên dương \(x\), gọi \(d(x)\) là số ước dương của \(x\). Một dãy số nguyên dương được gọi là dãy đẹp nếu số ước của các phần tử tăng thực sự theo thứ tự trong dãy, tức là \(d(b_1) < d(b_2) < \ldots < d(b_k)\).

Cho dãy \(a_1, a_2, \ldots, a_n\). Ta được xóa một số phần tử (giữ nguyên thứ tự các phần tử còn lại) để phần còn lại là một dãy đẹp. Hãy tìm độ dài lớn nhất của dãy đẹp có thể thu được (tức là số phần tử ít nhất phải xóa là \(n\) trừ đi giá trị này).

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\).

Output

• In ra một số nguyên: số phần tử lớn nhất của dãy đẹp thu được.

Constraints

• \(1 \le n \le 5 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)
• Subtask 1 (20%): \(n \le 20\), \(a_i \le 10^3\).
• Subtask 2 (40%): \(n \le 10^3\), \(a_i \le 10^6\).
• Subtask 3 (20%): \(n \le 5 \cdot 10^4\), \(a_i \le 10^6\).
• Subtask 4 (20%): không có ràng buộc thêm.

Sample Input 1

6
12 2 9 7 30 4

Sample Output 1

3

Explanation

Số ước của từng phần tử là \(6, 2, 3, 2, 8, 3\). Có thể giữ lại các phần tử \(2, 9, 30\) (số ước \(2 < 3 < 8\)) tạo thành dãy đẹp dài \(3\), và không có dãy đẹp nào dài hơn.