초☆초☆광☆속☆배☆달☆최☆속!!! 스피드★스타★카나데

안돼! 벌써 이런 시간이? 지각이야 지각! 이렇게 된 이상 소후란 파워로 광속을 돌파해서 BPM 999의 스피드스타가 되어야만 해!

— 카메리아 feat.나나히라, 「혼란소녀♥소프란쨩!!」

카나데는 $1$번 구간의 시작점에서 $1, 2, \cdots, N$번 구간 순서대로 총 $N$개의 구간으로 이루어진 도로를 지나 $N$번 구간 종점에 있는 카레 가게로 가야 한다!

스피드 스타 카나데는 BPM 999⁹⁹⁹ 의 속도로 달릴 수 있지만, 구간마다 BPM 제한 $A_i$가 걸려 있어 $i$번 구간에서는 $A_i$를 초과한 BPM으로 달릴 수 없다!

카나데는 $1$번 구간에서의 BPM을 $1$ 이상 $A_1$ 이하의 원하는 정수로 선택할 수 있으며, 각 $i$ $(2\leq i \leq N)$번 구간에 들어가기 직전 소후란 파워를 사용해서 BPM을 $1$ 이상 $A_i$ 이하의 원하는 정수로 바꿔 진입할 수 있다! 만약, 현재 BPM과 바꾸려는 BPM이 서로소 관계라면 소후란 파워로도 바꿀 수 없다!

카나데는 속도 위반을 하지 않으면서 각 구간에서의 BPM의 총합이 최대가 되게 BPM을 선택하며 달리고 싶다! 카나데를 위해 각 구간에서의 BPM의 총합의 최댓값을 구해주자!

첫 번째 줄에 구간의 개수 $N$이 주어진다! $(2 \leq N \leq 2\,000)$

두 번째 줄에 각 구간의 BPM 제한을 나타내는 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백을 사이에 두고 주어진다! $(2 \leq A_i \leq {999\,999\,999})$

첫 번째 줄에 가능한 BPM 총합의 최댓값을 출력하자!