Cho trước số nguyên dương \(N\) và dãy số nguyên \(a_1, a_2, \dots, a_N\). Một đoạn con \(a_L, a_{L+1}, a_{L+2}, \dots, 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ố. Trong toán học số nguyên tố là số chỉ có hai ước \(1\) và chính nó, ví dụ: \(3, 5, 11, \dots\) là số nguyên tố; \(4, 6, 15, \dots\) không phải 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_{L+2} + \dots + a_R\).

Yêu cầu

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

Input

Đọc từ bàn phím theo cấu trúc sau:

• 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, \dots, 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.

Example

6
9 5 -2 6 -1 1

8

Scoring

• 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\).