Xin cảm ơn DevGang đã cung cấp bộ đề, test và lời giải cho bài này.

Số nguyên tố là số nguyên dương lớn hơn ~1~ và chỉ có hai ước dương là ~1~ và chính nó. Ví dụ: ~2; 3; 7; 13~ là các số nguyên tố còn ~4; 6; 20~ không là số nguyên tố. Khôi đang học về số nguyên tố. Hôm nay, Thầy giáo cho một dãy số nguyên dương $A$ gồm $n$ phần tử ~A_{1}, A_{2} , \dots A_{n}~ và yêu cầu Khôi đếm số lượt đổi chỗ ít nhất các phần tử của dãy $A$ để tất cả các số nguyên tố trong dãy được gom vào một miền liên tiếp. Em hãy giúp Khôi tìm ra đáp án của bài toán nhé!

Dữ liệu vào

Đọc từ file văn bản DOMAIN.INP gồm:

• Dòng thứ nhất gồm một số nguyên dương $n$ ($1\le n\le10^{6}$).

• Dòng thứ hai gồm $n$ số nguyên dương $A_{1}$, $A_{2},...,A_{n}$ giữa hai số cách nhau một khoảng trắng ($1\le A_{i}\le10^{6}$, $1\le i\le n$).

Kết quả ra

Ghi ra văn bản DOMAIN.OUT một số nguyên duy nhất là số lượt đổi chỗ ít nhất tìm được.

Ràng buộc

• Có ~20\%~ test có $1\le n,$ $A_{i}\le10^{2}$, $1\le i\le n$.

• Có ~30\%~ test có $10^{2}<n,$ $A_{i}\le10^{3}$, $1\le i\le n$.</p>

• Có ~50\%~ test còn lại có giới hạn như trong đề.

Ví dụ

Dữ liệu

7
10 2 3 6 7 8 5

Kết quả

1

Giải thích

Đổi chỗ số ~6~ và số ~5~ để các số nguyên tố được gom vào một miền duy nhất.