Triple Interval Product Sum

Given a permutation \(a\) of length \(n\). For any three subintervals \( [l_1,r_1] \), \( [l_2,r_2] \), and \( [l_3,r_3] \) such that \(1 \le l_1 \le r_1 < l_2 \le r_2 < l_3 \le r_3 \le n\), define the minimum value in an interval \([l,r]\) as \(\min_{[l,r]}\) and the maximum as \(\max_{[l,r]}\).

Consider the expression \[ \max\Big(0,\min_{[l_2,r_2]} - \max_{[l_1,r_1]}\Big) \times \max\Big(0,\min_{[l_2,r_2]} - \max_{[l_3,r_3]}\Big), \] and compute the sum of this value over all valid triplets of subintervals. Output the result modulo \(9712176\).

Note: A permutation is a sequence of distinct integers from 1 to \(n\).

inputFormat

The first line contains an integer \(n\).
The second line contains \(n\) distinct integers representing the permutation \(a\).

outputFormat

Output a single integer — the sum modulo \(9712176\).

sample

3
1 2 3

0