题目描述

Y 同学定义了一串连续取模函数。给定正整数序列 $a_1,a_2,\dots,a_n$，对任意非负整数 $x$，令 $x_0=x$，并依次令 $x_i=x_{i-1}\bmod a_i$。他关心的是 $x_1+x_2+\cdots+x_n$ 的最大可能值。

虽然 $x$ 没有上界，但第一步之后的余数只可能落在有限范围内。困难之处在于，后续每次取模既可能保留当前高余数，也可能让某些较小余数在之后变得更优，不能只贪心选择当前最大余数。

请你求出所有非负整数 $x$ 中，上述和的最大值。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一行一个整数，表示最大可能值。

样例

样例输入 #1

3
5 3 2

样例输出 #1

6

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le n\le2\times10^5$，$1\le a_i\le10^{13}$。

特殊性质 A：保证 $a_i$ 单调不降。 特殊性质 B：保证 $a_i$ 单调不增。