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 取模的结果。

样例

输入

4
2
4
1
4

输出

109

提示

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

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题