给出一个正整数序列 a，长度为 n。定义一个连续子区间 [i, j] 的贡献为：区间最大值 × 区间最小值 × 区间长度。请求出所有满足 1<=i<=j<=n 的子区间的贡献之和，答案对 1000000000 取模。
例如序列为 2 4 1 4，可算得所有子区间贡献之和为 109。
第一行输入一个整数 n。
第 2 ~ n+1 行，每行一个整数，表示序列 a。
输出答案对 1000000000 取模后的结果。
4 2 4 1 4
109
分治：对区间取中点，枚举跨中点子区间并用两侧前缀最小/最大维护；也可用单调栈确定每个(最大值,最小值)组合的支配区间后按区间长度加权求和。（本题评测数据 n<=1000，O(n^2) 枚举即可通过）