{"problem":{"name":"「EZEC-14」众数 II","description":{"content":"给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$： - 初始时 $b$ 为空序列。 - 对于 $i=1,2,\\cdots,n$，我们依次向 $b$ 的尾部插入 $1,2,\\cdots,a_i$。 dXqwq 定义一个序列的**最小众数**为所有出现次数最大的数的最小值。例如 $[1,1,4,5,1,4]$ 的最小众数为 $1$，而 $[1,14,5,14,19,19,8","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9461"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的序列 $a$，我们通过以下方式构造序列 $b$：\n\n- 初始时 $b$ 为空序列。\n- 对于 $i=1,2,\\cdots,n$，我们依次向 $b$ 的尾部插入 $1,2,\\cdots,a_i$。\n\ndXqwq 定义一个序列的**最小众数**为所有出现次数最大的数的最小值。例如 $[1,1,4,5,1,4]$ 的最小众数为 $1$，而 $[1,14,5,14,19,19,8,10]$ 的最小众数为 $14$。\n\n你需要求出 $b$ 的每个子区间的**最小众数**的和。由于答案可能很大，你只需要输出它对 $998244353$ 取模后的值。\n\n## Input\n\n第一行输入一个整数 $n$。\n\n第二行输入 $n$ 个整数 $a_i$。\n\n## Output\n\n输出一个整数，代表 $b$ 的每个子区间的最小众数的和对 $998244353$ 取模的值。\n\n[samples]\n\n## Background\n\ndXqwq 是一个不可爱的男孩子。他在 NOI2022 中的众数一题定义了 $10^6$ 个 ``std::deque`` 并成功 MLE。\n\n## Note\n\n**【样例解释】**\n\n在第一个样例中，$b=[1,1,2,1,2,3]$。\n\n有 $15$ 个区间的最小众数为 $1$，$5$ 个区间的最小众数为 $2$，$1$ 个区间的最小众数为 $3$，因此答案为 $15\\times 1+5\\times 2+1\\times 3=28$。\n\n**【提示】**\n\n开 $10^6$ 个 ``std::deque`` 在空间限制为 512MB 时一定会 MLE。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n- Subtask 1（10 pts）：$\\sum a_i\\leq 100$。\n- Subtask 2（20 pts）：$\\sum a_i\\leq 10^3$。 \n- Subtask 3（20 pts）：$\\sum a_i\\leq 10^6$。\n- Subtask 4（10 pts）：$n\\leq 2$。\n- Subtask 5（20 pts）：$n\\leq 10^3$。\n- Subtask 6（10 pts）：$a_i\\leq 2$。\n- Subtask 7（10 pts）：无特殊限制。 \n\n对于 $100\\%$ 的数据，$1\\leq n\\leq 10^6$，$1\\leq a_i\\leq 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9461","tags":["洛谷原创","O2优化","洛谷月赛","链表","单调栈"],"sample_group":[["3\n1 2 3","28"],["9\n9 9 8 2 4 4 3 5 3","1912\n"]],"created_at":"2026-03-03 11:09:25"}}