Вам задан массив \(a_1, a_2, \dots, a_n\). Все \(a_i\) попарно различные.
Определим функцию \(f(l, r)\) следующим образом:
Посчитайте \(\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)\). Другими словами — сумму функций \(f\) для всех подотрезков массива \(a\) по модулю \(10^9+7\).
В первой строке содержится целое число \(n\) (\(1 \le n \le 5 \cdot 10^5\)) — длина массива \(a\).
Во второй строке содержится \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\), \(a_i \neq a_j\) for \(i \neq j\)) — массив \(a\).
Выведите единственное число — сумму функций \(f\) для всех подотрезков массива \(a\) по модулю \(10^9+7\).
Описание первого примера:
4 5 2 4 7
167
3 123456789 214365879 987654321
582491518
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач