#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 ,求

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

4
2
4
1
4
109

提示

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