Cho ~N~ số nguyên (vừa âm vừa dương). Một đoạn được gọi là đẹp nếu như vị trí của số đầu và số cuối của đoạn đó đều là số nguyên tố. Và nhiệm vụ mà thầy/cô giáo của LT giao cho đó là tìm đoạn đẹp có tổng lớn nhất trong ~N~ số nguyên kia. Và deadline cho LT là trước mùng 7 Tết.

Input

• Dòng đầu chứa số nguyên dương ~N~ ~(N \le 2)~,
• Dòng thứ 2 chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(a_i \le 10^6)~.

Output

• In ra một dòng duy nhất là kết quả của bài toán

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~N\le 10^2~.
• Subtask ~2~ (~30\%~ số điểm): ~N\le 3 * 10^3~.
• Subtask ~3~ (~20\%~ số điểm): ~N\le 10^5~

Ví dụ

Input

6
-6 7 6 7 -7 6

Output

13

Giải thích ví dụ

• Ở test ví dụ, có 6 đoạn thỏa mãn đoạn đẹp bao gồm

• 2 -> 2

• 3 -> 3
• 5 -> 5
• 2 -> 3
• 2 -> 5
• 3 -> 5

Đoạn có tổng lớn nhất là đoạn từ 2 -> 3 với tổng là 13