Cho dãy số nguyên \(a_1,a_2,..,a_n\), một đoạn \(a_L,a_{L+1},...,a_R \) (\(1 \leq L \leq R \leq n\) ) được gọi là đoạn đẹp nếu \(L, R\) đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(2 \leq n \leq 250000\))
• Dòng thứ hai chứa n số nguyên \(a_1,a_2,..,a_n\) (\(|a_i| \leq 10^6\))

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Ví dụ:

Input

5
-5 1 -3 3 1

Ouput

2