Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3] является попоследовательностью массива [1,2,3] , но [3,1] не является.
Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2] является подотрезком массива [1,2,3] , а [1,3] не является. Несложно заметить, что у массива длины n ровно
\( {n(n+1) \over 2}\) подотрезков.
Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a
i ≤ a
i+1.
Монотонностью массива назовем количество его возрастающих подотрезков.
Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10
9+7.
Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a
i ≤ 200000) — элементы массива a.
Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10
9+7.
Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:
- У массива [1] есть ровно один подотрезок и он является возрастающим.
- У массива [2] есть ровно один подотрезок и он является возрастающим.
- У массива [3] есть ровно один подотрезок и он является возрастающим.
- У массива [1,2] есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
- У массива [1,3] есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
- У массива [3,2] есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3] и [2] ) являются возрастающими.
- У массива [1,3,2] есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.
Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 3 2 |
15 |
| 2 |
3
6 6 6 |
12 |