Problem Description

Given a permutation \( a \) of length \( n \). Define the minimum value of \( a_i \) in a subinterval \([l, r]\) as \(\min_{[l, r]}\) and the maximum value as \(\max_{[l, r]}\). For all triples of subintervals \(([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\), find 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]})\) 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

A single line containing a positive integer, representing 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]})\) modulo \(9712176\).

Sample Input and Output

Sample Input #1

4
1 3 4 2

Sample Output #1

14

Sample Input #2

10
1 3 6 2 7 9 4 10 8 5

Sample Output #2

1992

Notes

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]})\) for all \(([l_1, r_1], [l_2, r_2], [l_3, r_3])\) is \(0 + 0 + 2 + 2 + 6 + 2 + 2 = 14\).

Data Range

This problem uses batched testing.

For \(100\%\) of the data: \(1 \leq n \leq 10^6\), \(1 \leq a_i \leq n\), and \(a\) is a permutation of \(\{1, 2, \dots, n\}\).

见题面 Input 部分

见题面 Output 部分