Cho một dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một dãy được gọi là dãy con của dãy ~a~ nếu ta xóa đi trong dãy ~a~ một số phần tử bất kỳ nào đó (có thể không xóa phần tử nào).

Yêu cầu: Tìm một dãy con của dãy ~a~ thỏa mãn hai điều kiện sau:

• Dãy con chỉ có một phần tử duy nhất hoặc dãy con có nhiều hơn một phần tử thì mỗi cặp hai phần tử liên tiếp nhau trong dãy con đều có ước chung lớn nhất khác ~1~;

• Tổng các phần tử của dãy con tìm được lớn nhất có thể.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(n \le 2 \cdot 10^5)~;

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9; 1 \le i \le n)~, mỗi số cách nhau một khoảng trống.

Output

Một số nguyên là tổng các phần tử của dãy con tìm được.

Scoring

Sample Input 1

8
2 3 6 5 10 15 7 21

Sample Output 1

55

Notes

Dãy con tìm được là:

~3, 6, 10, 15, 21~.