Назовем подпоследовательностью массива $$$a$$$ непустой массив $$$b$$$ такой, что он может быть получен из массива $$$a$$$ удалением нескольких (возможно, никаких) элементов массива $$$a$$$. Например, массив $$$[1, 3]$$$ является попоследовательностью массива $$$[1, 2, 3]$$$, но $$$[3, 1]$$$ не является.
Назовем подотрезком массива $$$a$$$ непустой массив $$$b$$$ такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива $$$a$$$. Например, $$$[1, 2]$$$ является подотрезком массива $$$[1, 2, 3]$$$, а $$$[1, 3]$$$ не является. Несложно заметить, что у массива длины $$$n$$$ ровно $$$\frac{n(n + 1)}{2}$$$ подотрезков.
Назовем массив $$$a$$$ длины $$$n$$$ возрастающим, если для любого $$$1 \leq i \lt n$$$ выполняется $$$a_i \lt a_{i + 1}$$$.
Монотонностью массива назовем количество его возрастающих подотрезков.
Дан массив $$$a$$$ длины $$$n$$$. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.
В первой строке задано целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — длина массива $$$a$$$.
Во второй строке заданы $$$n$$$ целых чисел ($$$1 \leq a_i \leq 200\,000$$$) — элементы массива $$$a$$$.
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю $$$10^9 + 7$$$.
3
1 3 2
15
3
6 6 6
12
В первом тестовом примере у массива есть $$$7$$$ подпоследовательностей:
Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину $$$1$$$.
