题目描述

小w在玩一个游戏。

给定一个长度为$n$的序列。其中第$i$个数是$a_i$。

小w会玩两轮游戏。

每一轮，他都会拿出这个序列的某个非空区间。他需要保证这两轮拿出的区间严格不相交，并且第一轮拿出的区间在第二轮区间的左边。

小w得到的收益是这两个区间的区间最小值。

现在，小w想要知道。所有可能的游戏情况的收益和多少。

答案对$10^9+7$取模。

输入格式

从标准输入读入数据。

输入第一行包含一个正整数 $n$。

接下来一行$n$个正整数，表示$a_i$。

输出格式

输出到标准输出。

输出一行一个整数，表示答案对$10^9+7$取模的值。

样例

输入

5
9 5 6 6 5

输出

179

子任务

对于$20\%$的数据，$n\le 50$。

对于$40\%$的数据，$n\le 300$。

对于$60\%$的数据，$n\le 3000$。

对于$100\%$的数据，$n\le 2\times 10^5,1\le a_i\le 10^9$。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载