3178. 搞操作

【题目描述】

小 D 擅长搞操作。

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

• $B$ 是一个空序列。

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

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

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入】

3
3 2 1

【样例输出】

58

【提示】

保证 $n \le 2 \times 10^5 ,1 \le A_i \le 10^6$。