{"problem":{"name":"E. Mod Mod Mod","description":{"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_.","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF889E"},"statements":[{"statement_type":"Markdown","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_.\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput a single integer — the maximum value of _f_(_x_, 1) over all nonnegative integers _x_.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 序列的长度。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 1013]) —— 序列的元素。\n\n## Output\n\n请输出一个整数 —— #cf_span[f(x, 1)] 在所有非负整数 #cf_span[x] 中的最大值。\n\n[samples]\n\n## Note\n\n在第一个例子中，你可以选择，例如，#cf_span[x = 19]。在第二个例子中，你可以选择，例如，#cf_span[x = 3] 或 #cf_span[x = 2]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF889E","tags":["binary search","dp","math"],"sample_group":[["2\n10 5","13"],["5\n5 4 3 2 1","6"],["4\n5 10 5 10","16"]],"created_at":"2026-03-03 11:00:39"}}