P4951.第3题-所有子区间前缀最小值之和
题目内容
给定一个长度为 n 的整数数组 a。对任意子数组区间 [l,r]，定义 f(l,r)=∑k=lr(mini∈[l,k]ai)。
请计算 ∑1≤l≤r≤nf(l,r) 并将结果对 109+7 取模后输出。
输入描述
每个测试文件包含多组测试数据。第一行输入一个整数 T（1≤T≤105）表示测试组数。接下来每组数据描述如下：
第一行输入一个整数 n（1≤n≤2×105）。
第二行输入 n 个整数 a1,a2,…,an（0≤ai≤109）。
保证所有测试数据的 n 之和不超过 3×105。
输出描述
对于每组测试数据，输出一行一个整数，表示 ∑1≤l≤r≤nf(l,r) 对 109+7 取模后的结果。
样例1
输入
2
3
2 1 3
4
3 3 3 3
输出
15
60
说明
样例一：a=[2,1,3]。
f(1,1)=min{2}=2
f(1,2)=min{2}+min{2,1}=2+1=3
f(1,3)=min{2}+min{2,1}+min{2,1,3}=2+1+1=4
f(2,2)=min{1}=1
f(2,3)=min{1}+min{1,3}=1+1=2
f(3,3)=min{3}=3
总和为 2+3+4+1+2+3=15
