{"problem":{"name":"「OICon-02」maxiMINImax","description":{"content":"给出一个长度为 $n$ 的排列 $a$。定义一个子区间 $[l,r]$ 中 $a_i$ 的最小值为 $\\min_{[l,r]}$，$a_i$ 的最大值为 $\\max_{[l,r]}$。对于所有子区间三元组 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 使得 $1\\leq l_1\\leq r_1<l_2\\leq r_2<l_3\\leq r_3\\leq n$，求 $\\max(0,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10173"},"statements":[{"statement_type":"Markdown","content":"给出一个长度为 $n$ 的排列 $a$。定义一个子区间 $[l,r]$ 中 $a_i$ 的最小值为 $\\min_{[l,r]}$，$a_i$ 的最大值为 $\\max_{[l,r]}$。对于所有子区间三元组 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 使得 $1\\leq l_1\\leq r_1<l_2\\leq r_2<l_3\\leq r_3\\leq n$，求 $\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})$ 之和，对 $9712176$ 取模。\n\n## Input\n\n第一行，一个正整数 $n$，表示排列的长度。\n\n第二行，$n$ 个正整数 $a$，表示给出的排列 $a$。\n\n## Output\n\n一行，一个正整数，表示 $\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})$ 之和，对 $9712176$ 取模。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n对于样例 $1$：\n\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,2],[3,3])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=0$；\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,2],[3,4])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=0$；\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,2],[4,4])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=2$；\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[2,3],[4,4])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=2$；\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,1],[3,3],[4,4])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=6$；\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([1,2],[3,3],[4,4])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=2$；\n* $([l_1,r_1],[l_2,r_2],[l_3,r_3])=([2,2],[3,3],[4,4])$：$\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})=2$。\n\n所有 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 的 $\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_1,r_1]})\\times\\max(0,\\min_{[l_2,r_2]}-\\max_{[l_3,r_3]})$ 总和为 $0+0+2+2+6+2+2=14$。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n| $\\text{Subtask}$ | 特殊性质 | $\\text{Score}$ |\n|:--:|:--:|:--:|\n| $1$ | $n\\leq60$ | $5$ |\n| $2$ | $n\\leq100$ | $9$ |\n| $3$ | $n\\leq200$ | $9$ |\n| $4$ | $n\\leq500$ | $9$ |\n| $5$ | $n\\leq2000$ | $19$ |\n| $6$ | $n\\leq6000$ | $11$ |\n| $7$ | $n\\leq10^5$ | $19$ |\n| $8$ | 无特殊限制 | $19$ |\n\n对于 $100\\%$ 的数据：$1\\leq n\\leq10^6$，$1\\leq a_i\\leq n$，保证 $a$ 为 $\\{1,2,\\dots,n\\}$ 的一个排列。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10173","tags":["线段树","O2优化","笛卡尔树","单调栈"],"sample_group":[["4\n1 3 4 2","14"],["10\n1 3 6 2 7 9 4 10 8 5","1992"]],"created_at":"2026-03-03 11:09:25"}}