P6406 [COCI 2014/2015 #2] Norma

给定一个正整数序列 $a_1,a_2,\cdots,a_n$ ，求 $$\sum_{i=1}^{n}\sum_{j=i}^{n}(j-i+1)\min(a_i,a_{i+1},\cdots,a_j)\max(a_i,a_{i+1},\cdots,a_j)$$

无

无

对于 $100\%$ 的数据，$1 \le n \leq 5\times 10^5$，$1 \le a_i \le 10^8$。