Problem Description

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<l_2\leq r_2<l_3\leq r_3\leq n$, compute 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]})$, and output the result modulo $9712176$.

Input Format

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 Format

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$.

4
1 3 4 2

14

10
1 3 6 2 7 9 4 10 8 5

1992

Hint

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.

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