#P8005. 「COCI 2014.11.08」NORMA

    ID: 7097 传统题 3000ms 64MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-分治算法前后缀最值同向双指针一维前缀和等差数列求和2014COCI

「COCI 2014.11.08」NORMA

题目描述

在 Mirko 生日那天,他收到了祖母送他的一个数列 AA。Mirko 居住的小镇上有一户人家专门收购数列(什么人啊)。对于一个数列 LL,它的价值 $v_L=\min\{L_i\}\times \max\{L_i\}\times \mathit{len}_L$(即数列的最小值,最大值与长度的积)。Mirko 计算了 AA 的所有子串的价值之和。
为了检查他的结果,你也要这么做。答案对 10910^9 取模。

输入格式

第一行一个正整数NN。
接下来 NN 行,每行一个正整数 aia_i,描述了 Mirko 的数列 AA。

输出格式

一行代表所有子串的价值之和对 10910^9 取模的结果。

2
1
3
16

所有子串分别为 (1),(3),(1,3)(1),(3),(1,3)。

4
2
4
1
4
109

所有子串分别为 $(2),(4),(1),(4),(2,4),(4,1),(1,4),(2,4,1),(4,1,4),(2,4,1,4)$。

6
8
1
3
9
7
4
1042

数据范围与提示

对于 40%40\% 的数据,N<5000N<5000;
对于 100%100\% 的数据,1≤N≤5×105,1≤ai≤1081\leq N \leq 5\times 10^5,1\leq a_i \leq 10^8。