P10173 "OICon-02" maxiMINImax

You are given a permutation $a$ of length $n$. Define the minimum value of $a_i$ in a subarray $[l,r]$ as $\min_{[l,r]}$, and the maximum value of $a_i$ in $[l,r]$ as $\max_{[l,r]}$. For all triples of subarrays $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ such that $1\leq l_1\leq r_1

The first line contains a positive integer $n$, the length of the permutation. The second line contains $n$ positive integers $a$, representing the given permutation $a$.

Output one line with a positive integer: the sum of $\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]})$ over all valid triples, modulo $9712176$.

### Sample Explanation For sample $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$. The total sum of $\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]})$ over all $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ is $0+0+2+2+6+2+2=14$. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | Special Property | $\text{Score}$ | |:--:|:--:|:--:| | $1$ | $n\leq60$ | $5$ | | $2$ | $n\leq100$ | $9$ | | $3$ | $n\leq200$ | $9$ | | $4$ | $n\leq500$ | $9$ | | $5$ | $n\leq2000$ | $19$ | | $6$ | $n\leq6000$ | $11$ | | $7$ | $n\leq10^5$ | $19$ | | $8$ | No special restrictions | $19$ | For $100\%$ of the data: $1\leq n\leq10^6$, $1\leq a_i\leq n$, and $a$ is guaranteed to be a permutation of $\{1,2,\dots,n\}$. Translated by ChatGPT 5