{"problem":{"name":"[语言月赛202303] M Function G","description":{"content":"对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下： $$ M(l, r) = \\begin{cases} \\left(M(l, \\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloor) \\bmod \\max(M(\\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloo","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P1"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3725"},"statements":[{"statement_type":"Markdown","content":"对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下：\n\n$$\nM(l, r) = \\begin{cases}\n\\left(M(l, \\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloor) \\bmod \\max(M(\\left \\lfloor \\dfrac{l + r}{2} \\right \\rfloor + 1, r), 7)\\right ) + \\left(a _ {\\left \\lfloor \\frac{l + r}{2} \\right \\rfloor} - 1 \\right ) & |r - l| > 5 \\\\\n\\max \\limits _ {l \\leq i \\leq r}{a _ i} & |r - l| \\leq 5\n\\end{cases}\n$$\n\n$\\max \\limits _ {l \\leq i \\leq r}{a _ i}$ 代表 $a _ l, a _ {l + 1}, \\cdots, a _ {r - 1}, a _ r$ 中的最大值。\n\n$\\left \\lfloor x \\right \\rfloor$ 代表 $\\leq x$ 的最大整数。比如 $\\left \\lfloor 4.2 \\right \\rfloor = 4$，$\\left \\lfloor 5 \\right \\rfloor = 5$。\n\n$\\max(x, y)$ 代表 $x, y$ 中的最大值。\n\n现在给定 $n$ 和 $a$，请你求出 $M(1, n)$。\n\n## Input\n\n输入共两行。\n\n第一行为一个整数 $n$。\n\n第二行为 $n$ 个整数 $a _ 1, a _ 2, \\cdots, a _ n$，对应题目中的正整数数列 $a$。\n\n## Output\n\n输出共一行一个整数，代表 $M(1, n)$ 的值。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n我们这里暂时使用 $\\max \\{a _ l, a _ {l + 1}, \\cdots, a _ r\\}$ 来表示 $a _ l, a _ {l + 1}, \\cdots, a _ r$ 中的最大值。\n\n$$\\begin{aligned} \nM(1, 10) &= M(1, 5) \\bmod \\max(M(6, 10), 7) + (a _ 5 - 1) \\\\ \n&= \\max \\{a _ 1, a _ 2 \\cdots, a _ 5\\} \\bmod \\max(\\max \\{a _ 6, a _ 7 \\cdots, a _ {10}\\}, 7) + (a _ 5 - 1) \\\\\n&= \\max \\{a _ 1, a _ 2 \\cdots, a _ 5\\} \\bmod \\max(84, 7) + (a _ 5 - 1) \\\\\n&= \\max \\{a _ 1, a _ 2 \\cdots, a _ 5\\} \\bmod 84 + (a _ 5 - 1) \\\\\n&= 91 \\bmod 84 + (a _ 5 - 1) \\\\\n&= 7 +  (a _ 5 - 1) \\\\\n&= 11\n\\end{aligned}$$\n\n### 数据规模与约定\n\n对于 $100\\%$ 的数据，保证 $1 \\leq n \\leq 5 \\times 10 ^ 5$，$1 \\leq a _ i \\leq 10 ^ 9$。\n\n| 测试点编号 | $n$ | $a _ i$ |  特殊性质 |\n| :----------: | :----------: | :----------: | :----------: |\n| $1 \\sim 2$ | $\\leq 10$ | $\\leq 100$ | 无 |\n| $3 \\sim 5$ | $\\leq 10 ^ 3$ | $\\leq 10 ^ 4$ | 无 |\n| $6$ | $\\leq 5 \\times 10 ^ 5$ | $\\leq 10 ^ 9$ | $a _ i = 1$ |\n| $7$ | $= 5$ | $\\leq 10 ^ 9$ | 无 |\n| $8 \\sim 10$ | $\\leq 5 \\times 10 ^ 5$ | $\\leq 10 ^ 9$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3725","tags":["2023","O2优化","函数与递归","语言月赛"],"sample_group":[["10\n3 72 26 91 5 84 18 29 50 23","11"]],"created_at":"2026-03-03 11:09:25"}}