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

Số nguyên tố là số chỉ có hai ước phân biệt 1 và chính nó, ví dụ: 3, 5, 11,..., là số nguyên tố; 4, 6, 15,..., không phải là số nguyên tố. Ví dụ: ~N = 4~, dãy số ~\{2, -4, 5, 7\}~ có các đoạn con đẹp lần lượt là: ~\{a_2\} = \{-4\}~ vì có ~L = 2, R = 2~ đều là số nguyên tố; ~\{a_3\} = \{5\}~ vì có ~L = 3, R = 3~ đều là số nguyên tố, ~\{a_2, a_3\} = \{-4, 5\}~ vì có ~L = 2, R = 3~ đều là số nguyên tố.

Tổng giá trị của đoạn con đẹp được tính bằng: ~a_L + a_{L+1} + ... + a_R~.

Yêu cầu: Hãy tìm đoạn con đẹp có tổng giá trị lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~2 \le N \le 10^6~);
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ (~|a_i| \le 10^6, 1 \le i \le N~), mỗi số cách nhau 1 khoảng trắng.

Output

Xuất ra màn hình một số nguyên duy nhất là tổng giá trị lớn nhất của đoạn con đẹp tìm được.

Sample Input 1

6
9 5 -2 6 -1 1

Sample Output 1

8

~N = 6~, dãy ~\{9, 5, -2, 6, -1, 1\}~ có các đoạn con đẹp là: ~\{5\}~, ~\{-2\}~, ~\{-1\}~, ~\{5, -2\}~, ~\{-2, 6, -1\}~, ~\{5, -2, 6, -1\}~, đoạn con đẹp có tổng lớn nhất là 8.

Subtasks

• Có 40% số test ứng với 40% số điểm thỏa mãn: ~N \le 10^2~;
• Có 30% số test khác ứng với 30% số điểm thỏa mãn: ~N \le 3000~;
• Có 30% số test còn lại ứng với 30% số điểm thỏa mãn: ~N \le 10^6~.