{"raw_statement":[{"iden":"statement","content":"You are given a sequence of integers _a_1, _a_2, ..., _a__n_. Let , and for 1 ≤ _i_ < _n_. Here, denotes the modulus operation. Find the maximum value of _f_(_x_, 1) over all nonnegative integers _x_."},{"iden":"input","content":"The first line contains a single integer _n_ (1 ≤ _n_ ≤ 200000) — the length of the sequence.\n\nThe second lines contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 1013) — the elements of the sequence."},{"iden":"output","content":"Output a single integer — the maximum value of _f_(_x_, 1) over all nonnegative integers _x_."},{"iden":"examples","content":"Input\n\n2\n10 5\n\nOutput\n\n13\n\nInput\n\n5\n5 4 3 2 1\n\nOutput\n\n6\n\nInput\n\n4\n5 10 5 10\n\nOutput\n\n16"},{"iden":"note","content":"In the first example you can choose, for example, _x_ = 19.\n\nIn the second example you can choose, for example, _x_ = 3 or _x_ = 2."}],"translated_statement":[{"iden":"statement","content":"给定一个整数序列 #cf_span[a1, a2, ..., an]。定义函数 f(x, i) 如下：f(x, n) = x，且对于 #cf_span[1 ≤ i < n]，有 f(x, i) = f(x, i+1)  \\%  a_i。这里，\\% 表示取模运算。求在所有非负整数 #cf_span[x] 中，#cf_span[f(x, 1)] 的最大值。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 序列的长度。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 1013]) —— 序列的元素。\n\n请输出一个整数 —— #cf_span[f(x, 1)] 在所有非负整数 #cf_span[x] 中的最大值。\n\n在第一个例子中，你可以选择，例如，#cf_span[x = 19]。\n\n在第二个例子中，你可以选择，例如，#cf_span[x = 3] 或 #cf_span[x = 2]。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 序列的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 1013]) —— 序列的元素。"},{"iden":"output","content":"请输出一个整数 —— #cf_span[f(x, 1)] 在所有非负整数 #cf_span[x] 中的最大值。"},{"iden":"examples","content":"输入\n2\n10 5\n输出\n13\n\n输入\n5\n5 4 3 2 1\n输出\n6\n\n输入\n4\n5 10 5 10\n输出\n16"},{"iden":"note","content":"在第一个例子中，你可以选择，例如，#cf_span[x = 19]。在第二个例子中，你可以选择，例如，#cf_span[x = 3] 或 #cf_span[x = 2]。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n \\in \\mathbb{N} $, $ n \\geq 1 $, and let $ a_1, a_2, \\dots, a_n \\in \\mathbb{N} $ with $ a_i \\geq 1 $.\n\nDefine the function $ f : \\mathbb{Z}_{\\geq 0} \\times \\{1, 2, \\dots, n\\} \\to \\mathbb{Z}_{\\geq 0} $ recursively by:\n\n$$\nf(x, i) =\n\\begin{cases}\nx \\bmod a_i & \\text{if } i = n, \\\\\nf(x \\bmod a_i, i+1) & \\text{if } 1 \\leq i < n.\n\\end{cases}\n$$\n\nFind:\n\n$$\n\\max_{x \\in \\mathbb{Z}_{\\geq 0}} f(x, 1)\n$$","simple_statement":null,"has_page_source":false}