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

Задан массив целых чисел $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$.