Chiến tranh giữa các vì sao

An đang chơi trò chơi “Chiến tranh giữa các vì sao”. Trong trò chơi, nhân vật của An cần phải thu được càng nhiều sức mạnh càng tốt từ các vì sao trong vũ trụ.

Có \(n\) vì sao được đánh số từ \(1\) đến \(n\) mà nhân vật của An có thể sẽ đi qua. Để không làm tổn hại đến sự toàn vẹn của vì sao, nhân vật không thể “quay ngược”, nghĩa là nếu nhân vật đã đi từ vì sao thứ nhất đến vì sao thứ tư, thì nhân vật không thể đến vì sao thứ hai hoặc thứ ba, nhân vật phải tiếp tục đi về phía trước. Tổng quát, nếu nhân vật đang ở vì sao \(i\) thì nhân vật chỉ có thể đi đến vì sao \(j > i\).

Với mỗi hành tinh \(i\) có một tham số \(a_i\). Khi nhân vật của An đi từ hành tinh \(i\) đến hành tinh \(j\), nó sẽ nhận thêm một sức mạnh \(\gcd(a_i, a_j)\), trong đó \(\gcd(a_i, a_j)\) là ước chung lớn nhất của \(a_i\) và \(a_j\). Lúc bắt đầu trò chơi, nhân vật của An có \(1\) đơn vị sức mạnh và xuất phát từ vì sao \(1\). Mục tiêu của An là đưa nhân vật đến vì sao \(n\) với tổng sức mạnh lớn nhất. Cụ thể là tìm một dãy các chỉ số \(1 = i_1 < i_2 < \dots < i_k = n\), sao cho tổng sau lớn nhất:

Hãy giúp An tính tổng sức mạnh lớn nhất mà nhân vật của anh ta có thể nhận được.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 2 \times 10^5)\) là số vì sao.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 2 \times 10^5 + 3)\) là các tham số của các vì sao.

Output

• Ghi ra một số nguyên là tổng sức mạnh lớn nhất mà nhân vật của An có thể nhận được.

Input

%
4
5 1 1 5

Output

%
6

Input

%
5
6 4 15 9 10

Output

%
9

Notes

Trong ví dụ đầu tiên, An sẽ di chuyển nhân vật đi từ vì sao \(1\) đến vì sao \(4\). Chú ý rằng, ban đầu nhân vật có \(1\) đơn vị sức mạnh. Tổng sức mạnh của nhân vật sẽ là: \(1 + \gcd(5, 5) = 6\).

Trong ví dụ thứ hai, An sẽ di chuyển nhân vật từ vì sao \(1\) đến vì sao \(3\), rồi đến vì sao \(5\). Tổng sức mạnh mà anh ta nhận được sẽ là: \(1 + \gcd(6, 15) + \gcd(15, 10) = 9\).

Scoring

• Có \(20\%\) số test ứng với \(20\%\) số điểm thỏa mãn: \(n \le 20\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(n \le 1000\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(a_i\) là các số nguyên tố, với mọi \(i = 1, 2, \dots, n\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thỏa mãn: \(n \le 2 \times 10^4\) và \(a_i \le 100\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm: Không có thêm ràng buộc nào.