Nguồn: Học sinh Giỏi THPT Hà Nội năm 2023 - 2024

Cho một dãy số gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) có giá trị không vượt quá \(10^6\). Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Input

Dữ liệu vào từ tệp văn bản DAYCON.INP:

• Dòng đầu tiên gồm một số nguyên dương \(N \ (N \le 10^6)\) là số lượng phần tử của dãy số;
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, ..., a_N\) lần lượt mô tả các phần tử của dãy số.

Output

Kết quả ra tệp văn bản DAYCON.OUT:

• Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra -1.

Examples

10
3 4 8 4 5 6 1 7 4 6

4

Note

• Chọn dãy con từ vị trí thứ \(5\) đến vị trí thứ \(8\): \(5, 6, 1, 7\).

Constraint

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thoả mãn: \(N \le 10^3; \ a_i \le 10^3\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thoả mãn: \(N \le 10^6; \ a_i \le 10^3\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.