← 返回题目列表

Codeforces · 889/E

E. 模组模组模组

中文机器翻译题面 查看原题

给定一个整数序列 a1, a2, ..., an。设 $$f(x,n) = x \bmod a_n$$,且 $$f(x,i) = (x \bmod a_i) + f(x \bmod a_i, i+1)$$,1 ≤ i < n。这里,$$\bmod$$ 表示模运算。求所有非负整数 x 上 f(x, 1) 的最大值。

输入

第一行包含一个整数 n (1 ≤ n ≤ 200000) — 序列的长度。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1013) — 序列的元素。

输出

输出单个整数 — 所有非负整数 x 上 f(x, 1) 的最大值。

示例

输入 #1

2
10 5

输出 #1

13

输入 #2

5
5 4 3 2 1

输出 #2

6

输入 #3

4
5 10 5 10

输出 #3

16

注意

在第一个示例中,您可以选择 x = 19。

在第二个示例中,您可以选择 x = 3 或 x = 2。