给定一个整数序列 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。