Cho dãy số nguyên ~a_1,a_2,\ldots,a_N~. Một đoạn con ~a_L,a_{L+1},\ldots,a_R~ được gọi là đẹp nếu cả ~L~ và ~R~ đều là số nguyên tố.

Yêu cầu

Tìm tổng lớn nhất của một đoạn con đẹp.

Input

Dòng đầu chứa số nguyên dương ~N~.

Dòng thứ hai chứa ~N~ số nguyên ~a_i~.

Output

In ra tổng lớn nhất.

Subtask

• 40% số điểm: ~N \le 10^2~.
• 30% số điểm: ~N \le 3000~.
• 30% số điểm: ~2 \le N \le 10^6~, ~|a_i| \le 10^6~.

Ví dụ

6
9 5 -2 6 -1 1

8