eolymp
Competitions

2021-2022 ICPC, SEERC, 1/8 Final

Коли немає чим зайнятись, а вдома лише перестановка

Дана перестановка $(p_1, p_2, \ldots, p_n)$ чисел від $1$ до $n$. З нею ви можете робити наступну операцію: \begin{itemize} \item Ви можете переставити місцями два \textbf{сусідні} елементи $p$. Ця операція займає рівно одну секунду. \end{itemize} За одну ітерацію ви робите наступне: \begin{itemize} \item Розглянемо перестановку $(q_1, q_2, \ldots, q_n)$, що знаходиться \textbf{прямо перед} $(p_1, p_2, \ldots, p_n)$ в лексикографічному порядку, тобто $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)$. \item Перетворимо перестановку $p$ в перестановку $q$, за мінімально можливу кількість операцій. Наприклад, щоб перетворити $(1, 4, 2, 3)$ в $(1, 3, 4, 2)$, потрібно мінімум $2$ операції: $(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2)$. \end{itemize} Ви застосовуєте до отриманої перестановки $p$ дану ітерацію, поки вона не стане тотожною перестановкою (тобто рівною $(1, 2, 3, \ldots, n))$. Скільки часу це займе? Оскільки це число може бути дуже великим, виведіть його за модулем $10^9+7$. Перестановка $p$ вважається лексикографічно меншою за перестановку $q$, якщо існує такий індекс $i$, що $p_j = q_j$ для всіх $j<i$, а також $p_i<q_i$. \InputFile Перший рядок містить єдине число $n$ ($1 \le n \le 2\cdot 10^5$)--- довжину перестановки. Другий рядок містить $n$ цілих чисел $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, всі числа попарно різні) --- елементи перестановки. \OutputFile Виведіть кількість секунд, яка пройде, поки процес не завершиться, за модулем $10^9+7$. \Note В першому прикладі маємо: $(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2)$: $2$ секунди. $(1, 3, 4, 2) \to (1, 3, 2, 4)$: $1$ секунда. $(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3)$: $2$ секунди. $(1, 2, 4, 3) \to (1, 2, 3, 4)$: $1$ секунда. Всього $6$ секунд.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
4
1 4 2 3
Output example #1
6
Input example #2
6
6 5 4 3 2 1
Output example #2
1423
Author Anton Trygub