Số đặc biệt (Câu 1 đề thi HSG Huyện Diễn Châu 2023)

Bài: Số đặc biệt

Khi còn học ở trường THCS, An rất thích môn toán, đặc biệt là các bài toán về số học. Do đó, khi được học về dãy số gồm \(N\) số nguyên \(a_1, a_2, a_3, \dots, a_N\), An đưa ra quan niệm một số \(a_i\) (\(1 < i < N\)) trong dãy là số đặc biệt nếu \(a_{i-1}\) và \(a_{i+1}\) đều là số nguyên tố.

Yêu cầu: Bạn hãy lập trình giải bài toán giúp An chỉ ra vị trí số đặc biệt cuối cùng (nếu có) trong dãy.

Input

• Nhập từ bàn phím một dãy \(N\) (\(0 < N < 10^5\)) số nguyên, cách nhau ít nhất một dấu cách. Các số nguyên trong dãy có giá trị tuyệt đối nhỏ hơn \(32767\).

Output

• In ra màn hình một số duy nhất là vị trí tìm được, hoặc số \(0\) nếu không tìm được.

Ràng buộc

• 30% số test tương ứng với 30% số điểm có \(1 < N \le 10^2\).
• 30% số test tương ứng với 30% số điểm có \(10^2 < N \le 10^3\).
• 40% số test tương ứng với 40% số điểm có \(10^3 < N \le 10^5\).

Example 1

Input

-2 238 5 6 7 0 -12 31 25 23 8

Output

9

Giải thích: Số \(25\) ở vị trí thứ \(9\) là số mà có số trước đó là \(31\) và số sau nó là \(23\) đều là số nguyên tố.

Example 2

Input

-21 654 54 26 70 0 -122 342 71 23 854

Output

0

Giải thích: Dãy trên không có số nào thỏa mãn điều kiện bài toán.