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

小花想认真观察序列

Description

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

对于一个序列 {an}\{a_n\},ta 用递归法定义了三个函数如下:

p(l,r)={0 l>r 1 l=r p(l,r1)+1 l<rp(l,r)= \begin{cases} 0 & \text{ $l>r$ } \\ 1 & \text{ $l=r$ } \\ p(l,r-1)+1 & \text{ $l<r$} \\ \end{cases}

h(l,r)={0 l>r ar l=r max{ar,h(l,r1)} l<r h(l,r)= \begin{cases} 0 & \text{ $l>r$ } \\ a_r & \text{ $l=r$ } \\ \max\{a_r,h(l,r-1)\} & \text{ $l<r$ } \end{cases}

w(l,r)={0 l>r ar l=r min{ar,w(l,r1)} l<r w(l,r)= \begin{cases} 0 & \text{ $l>r$ } \\ a_r & \text{ $l=r$ } \\ \min\{a_r,w(l,r-1)\} & \text{ $l<r$ } \end{cases}

之后小花给了你一个式子

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

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

Format

Input

11 行一个整数 nn 表示序列长度。

22 行共 nn 个整数 aia_i 用于描述这个序列的元素。

Output

11 行一个整数 ansans 表示答案。

Samples

4
2 4 1 4
109
6
8 1 3 9 7 4
1042

输入数据3

见样例文件 ex.in

输出数据3

见样例文件 ex.out

Constraints

对于前 20%20\% 的数据,保证 1n30001 \le n \le 3000

对于前 40%40\% 的数据,保证 1n5×1041 \le n \le 5\times 10^4

对于另外 20%20\% 的数据,保证 1ai30001\le a_i \le 3000

对于全部 100%100\% 的数据,保证 1n5×1051 \le n \le 5 \times 10^51ai1091 \le a_i \le 10^9