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

Вхідні дані

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

Вихідні дані

Виведіть суму $min (a_{i}, a_{i + 1}, ..., a_{j})$ \min(a_i, a_{i+1}, ..., a_j) за модулем $1 0^{9} + 7$ 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\}, \{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$ 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Сума всіх мінімумів дорівнює $17$ .

Приклад 1

Loading

Приклад 2

Loading