题目描述

给出一个长度为 $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$ 个正整数 $a$，表示给出的排列 $a$。

输出格式

一行，一个正整数，表示 $\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$ 取模。

4
1 3 4 2

14

10
1 3 6 2 7 9 4 10 8 5

1992

提示

样例解释

对于样例 $1$：

• $([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$；
• $([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$；
• $([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$；
• $([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$；
• $([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$；
• $([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$；
• $([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$。

所有 $([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$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\leq n\leq10^6$，$1\leq a_i\leq n$，保证 $a$ 为 $\{1,2,\dots,n\}$ 的一个排列。