4025 - [COCI2014-2015#2] Norma

给定 n 个正整数 a_1,a_2,\dots,a_n，求：

\sum\limits_{i=1}^n\sum\limits_{j=i}^n (j-i+1)\max(a_i,a_{i+1},\dots,a_j)\min(a_i,a_{i+1},\dots,a_j)

答案对 1000000000 取模。

第一行一个整数 n。

接下来 n 行，每行一个正整数，表示序列 a_1,a_2,\dots,a_n。

输出为一个数，即答案对 1000000000 取模的结果。

对于 100\% 的数据，1 \le n \le 5\times10^5,1 \le a_i \le 10^8。