Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(a_{1},a_{2},\ldots,a_{n}\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) là tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách loại một số trong dãy số đã cho để tổng các số mũ nhỏ nhất có thể.

Ví dụ: Co dãy số gồm 4 số: \(1,\ 2,\ 4,\ 10\). Có 2 cách bỏ đều cho tổng số mũ bằng 3 là nhỏ nhất.

+ Cách 1: Loại bỏ số \(4\), ta có \(P = 1 \times 2 \times 10 = 20 = 2^{2} \times 5\), có tổng số mũ bằng 3

+ Cách 2: Loại bỏ số \(10\), ta có \(P = 1 \times 2 \times 4 = 8 = 2^{3}\), có tổng số mũ bằng 3

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq {5 \times 10}^{5})\)

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{6})\)

Kết quả:

+ Ghi một số nguyên duy nhất cho biết kết quả bài toán

Ví dụ:

Ràng buộc:

+ Có 30% số test có \(n \leq 10;a_{i} \leq 8\);

+ Có 30% số test khác có \(n \leq 10^{4};a_{i} \leq 10^{6}\);

+ Có 40% số test còn lại không có ràng buộc gì thêm