{"raw_statement":[{"iden":"statement","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$ 取模。"},{"iden":"input","content":"第一行，一个正整数 $n$，表示排列的长度。\n\n第二行，$n$ 个正整数 $a$，表示给出的排列 $a$。"},{"iden":"output","content":"一行，一个正整数，表示 $\\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$ 取模。"},{"iden":"note","content":"### 样例解释\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\\}$ 的一个排列。"}],"translated_statement":null,"sample_group":[["4\n1 3 4 2","14"],["10\n1 3 6 2 7 9 4 10 8 5","1992"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}