You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

给你一个长度为$n$的排列$p$
计算所有子数组的最长递减子数组的长度之和
结果可能很大，请输出答案对$1e9+7$取模之后的答案

子数组是指在一个数组中，选择一些连续的元素组成的新数组。子数组必须包含至少一个元素，并且这些元素在原数组中的顺序保持不变。

最长递减子数组即数组所有子数组中严格递减的数组中最长的数组，例如数组$[2,3,1]$的最长递减子数组为$[3,1]$

Format

Input

每个测试点只有一组测试数据：
第一行有一个正整数$n(3 \leq n \leq 500000)$代表排列的长度
第二行有$n$个正整数，$p[1],p[2], \dots ,p[n](1 \leq p_i \leq n，p_i互不相同)$，代表给出的排列

Output

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

Samples

3
2 3 1 

8