Сума мінімумів підмасиву

Задано масив цілих чисел $A$. Знайдіть суму $min(a_i,a_{i+1},...,a_j)$ для кожної пари $(i,j)$, де $1\le i\le j\le n$.

Вхідні дані

Перший рядок містить розмір $n(1\le n\le 10^5)$ масиву $A$. Другий рядок містить $n$ цілих чисел $a_i(1\le a_i\le 10^5)$ — елементи масиву.

Вихідні дані

Виведіть суму $min(a_i,a_{i+1},...,a_j)$ за модулем $10^9+7$.

Приклади

Розглянемо перший тест.

Розглянемо всі підмасиви: $\{3\},\{1\},\{2\},\{4\},\{3,1\},\{1,2\},\{2,4\},\{3,1,2\},\{1,2,4\},\{3,1,2,4\}$.

Їх мінімуми дорівнюють $3,1,2,4,1,1,2,1,1,1$. Сума всіх мінімумів дорівнює $17$.