3178. 搞操作

【题目描述】

小 D 擅长搞操作。

对于一个序列 A（下标从 0 编号），小 D 可以做如下操作获得序列 B：

• B 是一个空序列。

• 从 0 至 length(A) - 1 枚举 i，从 0 至 length(A) - i - 1 枚举 j。

• 对于枚举的每一个 (i, j)，依次将 max$ A_k$ (k=j-i+j)加入 B 的末尾。

小 D 太喜欢操作了，于是按照同样的方法由 B 操作出了序列 C。

小 D 想知道 ∑$C_i$(i=0-length(C)-1)，对 $10^9$ + $7 $取模。

【输入格式】

第一行，正整数 n，代表 A 的长度。

第二行， n 个正整数，代表序列 A。

【输出格式】

输出一行，一个整数，代表取模后的答案。

【样例输入】

3
3 2 1

【样例输出】

58

【提示】

保证$ n$ ≤ $2 $∗ $10^5$， $1$ ≤ $A_i$ ≤$ 10^6$。