Trong một kỳ thi, việc sáng tạo bài dễ nhất trong bộ đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

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.

Yêu cầu: Tìm tổng lớn nhất của đoạn đẹp.

Input

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

Output

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

Sample Input 1

6
9 5 -2 6 -1 1

Sample Output 1

8

Subtasks

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