Містер IP знайшов цілий масив довжини . Він вільний на вихідних, тому знайшов собі заняття:
Для кожного підмасиву (1 \le l \le r \le n) визначте
Тепер його цікавить значення
Оскільки воно може бути дуже великим, він хоче знати лише його залишок при діленні на 10^9 + 7 (іншими словами, S \mod (10^9 + 7)). Допоможіть йому обчислити це!
Перший рядок містить єдине ціле число (1 \le n \le 5 \cdot 10^5) — довжина масиву.
Другий рядок містить цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le 10^6).
Виведіть єдине ціле число — значення залишку за модулем 10^9 + 7.
Приклад 1
Приклад 2
У першому прикладі всі підмасиви та їх внески:
: \min = 1, \max = 1, внесок 1 \cdot 1 = 1
: \min = 1, \max = 2, внесок 1 \cdot 2 = 2
[1,2,3]: \min = 1, \max = 3, внесок 1 \cdot 3 = 3
: \min = 2, \max = 2, внесок 2 \cdot 2 = 4
: \min = 2, \max = 3, внесок 2 \cdot 3 = 6
: \min = 3, \max = 3, внесок 3 \cdot 3 = 9
Сума всіх внесків дорівнює 1 + 2 + 3 + 4 + 6 + 9 = 25.
У кожному блоці тести оцінюються незалежно.
( балів): n \leq 2000;
( балів): a_i \leq a_{i+1} для всіх 1 \leq i \leq n-1;
( балів): серед елементів не більше різних значень;
( балів): n \leq 10^5;
( балів): без додаткових обмежень.