Cho dãy số nguyên dương ~A~ gồm ~n~ phần tử. Cần đổi chỗ ít nhất các phần tử để tất cả số nguyên tố trong dãy nằm trong một đoạn liên tiếp.

Yêu cầu

Tìm số lượt đổi chỗ ít nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_i~ ~(1 \le A_i \le 10^9)~.

Output

In ra số lượt đổi chỗ ít nhất.

Subtask

• Có ~50\%~ số test có ~n \le 10^3~, ~A_i \le 10^3~.
• Có ~30\%~ số test có ~n \le 10^4~, ~A_i \le 10^5~.
• Có ~20\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

7
10 2 3 6 7 8 5

1