[COCI 2014/2015 #2] Norma - 题目详情 - 33OJ

ID: 6644

远端评测题

2000ms

64MiB

难度: 6

上传者:

标签>

2014

递归

O2优化

分治

COCI（克罗地亚）

题目描述

给定一个正整数序列 $a_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)

输入格式

第一行一个整数 $n$ 。
接下来 $n$ 行，每行一个正整数，表示输入序列 $a_1,a_2,\cdots,a_n$ 。

输出格式

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

输入数据 1

输出数据 1

提示

对于 $100\%$ 的数据， $1 \le n \leq 5\times 10^5$ ， $1 \le a_i \le 10^8$ 。