题目描述
小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}$
