#C. 小花想认真观察序列

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

众所周知，OI 十分喜欢考察序列有关的问题。在备考 2077 年 NOIP 的小花自然想锻炼一下对序列的感知能力。

对于一个序列 $\{a_n\}$ ，ta 用递归法定义了三个函数如下：

$$p(l,r)= \begin{cases} 0 & \text{ $l>r$ } \\ 1 & \text{ $l=r$ } \\ p(l,r-1)+1 & \text{ $lr$ } \\ a_r & \text{ $l=r$ } \\ \max\{a_r,h(l,r-1)\} & \text{ $lr$ } \\ a_r & \text{ $l=r$ } \\ \min\{a_r,w(l,r-1)\} & \text{ $l<r$ } \end{cases} $$

之后小花给了你一个式子

\sum_{i=1}^n\sum_{j=1}^n h(i,j)w(i,j)p(i,j)

小花希望你能告诉 ta 这个式子在 $\bmod~ (10^9)$ 意义下的值是多少？

Format

Input

第 $1$ 行一个整数 $n$ 表示序列长度。

第 $2$ 行共 $n$ 个整数 $a_i$ 用于描述这个序列的元素。

Output

共 $1$ 行一个整数 $ans$ 表示答案。

Samples

4
2 4 1 4

6
8 1 3 9 7 4

输入数据3

见样例文件 ex.in。

输出数据3

见样例文件 ex.out。

Constraints

对于前 $20\%$ 的数据，保证 $1 \le n \le 3000$ 。

对于前 $40\%$ 的数据，保证 $1 \le n \le 5\times 10^4$ 。

对于另外 $20\%$ 的数据，保证 $1\le a_i \le 3000$ 。

对于全部 $100\%$ 的数据，保证 $1 \le n \le 5 \times 10^5$ ， $1 \le a_i \le 10^9$ 。

云斗杯.十一月 NOIP模拟赛

未参加

状态: 已结束
规则: IOI
题目: 4
开始于: 2022-11-19 18:00
结束于: 2022-11-21 0:00
持续时间: 30 小时
主持人: shijingyao
参赛人数: 145