| Codeforces Round 232 (Div. 1) |
|---|
| Закончено |
Вам дана перестановка p. Посчитайте суммарное количество инверсий во всех перестановках, лексикографически не больших данной.
Поскольку это число может быть очень большим, выведите его по модулю 1000000007 (109 + 7).
В первой строке задано единственное целое число n (1 ≤ n ≤ 106) — длина перестановки. Во второй строке заданы n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n).
Выведите единственное число — ответ на задачу по модулю 1000000007 (109 + 7).
2
2 1
1
3
2 1 3
2
Перестановкой p длины n называется последовательность, состоящая из n различных целых чисел, каждое из которых от 1 до n.
Инверсией перестановки p1, p2, ..., pn называется пара индексов (i, j), такая что i < j и pi > pj.
Перестановка a лексикографически не больше перестановки b, если a = b или существует такое число i, для которого выполняется логическое условие: 
И (ai < bi).
