Дана перестановка (p1,p2,…,pn) чисел від 1 до n.
З нею ви можете робити наступну операцію:
Ви можете переставити місцями два сусідні елементи p. Ця операція займає рівно одну секунду.
За одну ітерацію ви робите наступне:
Розглянемо перестановку (q1,q2,…,qn), що знаходиться прямо перед (p1,p2,…,pn) в лексикографічному порядку, тобто q лексикографічно менша за p і не існує жодної перестановки "між ними". Наприклад, для p=(2,3,1) q=(2,1,3), для p=(3,1,2,4) q=(2,4,3,1), а для p=(1,4,2,3) q=(1,3,4,2).
Перетворимо перестановку p в перестановку q, за мінімально можливу кількість операцій. Наприклад, щоб перетворити (1,4,2,3) в (1,3,4,2), потрібно мінімум 2 операції: (1,4,2,3)→(1,4,3,2)→(1,3,4,2).
Ви застосовуєте до отриманої перестановки p дану ітерацію, поки вона не стане тотожною перестановкою (тобто рівною (1,2,3,…,n)). Скільки часу це займе? Оскільки це число може бути дуже великим, виведіть його за модулем 109+7.
Перестановка p вважається лексикографічно меншою за перестановку q, якщо існує такий індекс i, що pj=qj для всіх j<i, а також pi<qi.
Перший рядок містить єдине число n (1≤n≤2⋅105)— довжину перестановки.
Другий рядок містить n цілих чисел p1,p2,…,pn (1≤pi≤n, всі числа попарно різні) — елементи перестановки.
Виведіть кількість секунд, яка пройде, поки процес не завершиться, за модулем 109+7.
В першому прикладі маємо:
(1,4,2,3)→(1,4,3,2)→(1,3,4,2): 2 секунди.
(1,3,4,2)→(1,3,2,4): 1 секунда.
(1,3,2,4)→(1,2,3,4)→(1,2,4,3): 2 секунди.
(1,2,4,3)→(1,2,3,4): 1 секунда.
Всього 6 секунд.