Mod Mod Mod

题意翻译

$$f(x,n) = x \mod a_n$$ $$f(x,i) = ( x \mod a_i ) + f(x \mod a_i,i+1)$$ 给出a序列，当x取遍所有非负整数时$f(x,1)$的最大值。

题目描述

You are given a sequence of integers $ a_{1},a_{2},...,a_{n} $ . Let , and  for $ 1<=i&lt;n $ . Here,  denotes the modulus operation. Find the maximum value of $ f(x,1) $ over all nonnegative integers $ x $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1<=n<=200000 $ ) — the length of the sequence. The second lines contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{13} $ ) — the elements of the sequence.

输出格式

Output a single integer — the maximum value of $ f(x,1) $ over all nonnegative integers $ x $ .

输入输出样例

输入样例 #1

2
10 5

输出样例 #1

13

输入样例 #2

5
5 4 3 2 1

输出样例 #2

6

输入样例 #3

4
5 10 5 10

输出样例 #3

16

说明

In the first example you can choose, for example, $ x=19 $ . In the second example you can choose, for example, $ x=3 $ or $ x=2 $ .