F. Скалярные запросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2, \dots, a_n$$$. Все $$$a_i$$$ попарно различные.

Определим функцию $$$f(l, r)$$$ следующим образом:

  • создадим массив $$$b_1, b_2, \dots, b_{r - l + 1}$$$, где $$$b_i = a_{l - 1 + i}$$$;
  • отсортируем массив $$$b$$$ в порядке возрастания;
  • результатом функции $$$f(l, r)$$$ назовем значение $$$\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$$$.

Посчитайте $$$\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
Примечание

Описание первого примера:

  • $$$f(1, 1) = 5 \cdot 1 = 5$$$;
  • $$$f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$$$;
  • $$$f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$$$;
  • $$$f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$$$;
  • $$$f(2, 2) = 2 \cdot 1 = 2$$$;
  • $$$f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$$$;
  • $$$f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$$$;
  • $$$f(3, 3) = 4 \cdot 1 = 4$$$;
  • $$$f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$$$;
  • $$$f(4, 4) = 7 \cdot 1 = 7$$$;