Cho dãy số nguyên ~a_1, a_2, \dots, a_n~, một đoạn ~a_L, a_{L+1}, \dots, a_R~ (~1 \le L \le R \le n~) được gọi là đoạn đẹp nếu tất cả các phần tử trong đoạn đề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 một đ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, \dots, 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