#P6406. [COCI 2014/2015 #2] Norma

    ID: 6644 远端评测题 2000ms 64MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2014递归O2优化分治COCI(克罗地亚)

[COCI 2014/2015 #2] Norma

题目描述

给定一个正整数序列 a1,a2,,ana_1,a_2,\cdots,a_n ,求

i=1nj=in(ji+1)min(ai,ai+1,,aj)max(ai,ai+1,,aj)\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)

输入格式

第一行一个整数 nn
接下来 nn 行,每行一个正整数,表示输入序列 a1,a2,,ana_1,a_2,\cdots,a_n

输出格式

输出答案对 10910^9 取模后的结果。

输入数据 1

4
2
4
1
4

输出数据 1

109

提示

对于 100%100\% 的数据,1n5×1051 \le n \leq 5\times 10^51ai1081 \le a_i \le 10^8