Cho dãy số nguyên ~a_1, a_2, . . . , a_n~. Một đoạn ~a_L, a_{L+1}, . . . , a_R~ ~(1 \le L \le R \le 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.

Dữ liệu

Dòng 1: số nguyên ~n \ge 2~. Dòng 2: ~n~ số nguyên ~a_i~ ~(|ai| \le 10^6)~

Kết quả

In ra đoạn đẹp có tổng nhất thỏa điều kiện đề bài.

Ví dụ.

Input

6
9 5 -2 6 -1 1

Output

8

Subtask.

• ~40\%~: ~n \le 100~

• ~30\%~: ~n \le 3000~

• ~30\%~: ~n \le 10^6~