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

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

2 seconds

256 megabytes

Very hard

Дана перестановка $(p_{1}, p_{2}, \dots, p_{n})$ (p_1, p_2, \ldots, p_n) чисел від $1$ до $n$ .

З нею ви можете робити наступну операцію: переставити місцями два сусідні елементи $p$ . Ця операція займає рівно одну секунду.

За одну ітерацію ви робите наступне:

Розглянемо перестановку $(q_{1}, q_{2}, \dots, q_{n})$ (q_1, q_2, \ldots, q_n), що знаходиться прямо перед $(p_{1}, p_{2}, \dots, p_{n})$ (p_1, p_2, \ldots, p_n) в лексикографічному порядку, тобто $q$ лексикографічно менша за $p$ і не існує жодної перестановки "між ними". Наприклад, для $p = (2, 3, 1)$ p = (2, 3, 1): $q = (2, 1, 3)$ q = (2, 1, 3), для $p = (3, 1, 2, 4)$ p = (3, 1, 2, 4): $q = (2, 4, 3, 1)$ q = (2, 4, 3, 1), а для $p = (1, 4, 2, 3)$ p = (1, 4, 2, 3): $q = (1, 3, 4, 2)$ q = (1, 3, 4, 2).

Перетворимо перестановку $p$ в перестановку $q$ , за мінімально можливу кількість операцій. Наприклад, щоб перетворити $(1, 4, 2, 3)$ (1, 4, 2, 3) в $(1, 3, 4, 2)$ (1, 3, 4, 2), потрібно мінімум $2$ операції: $(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2)$ (1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2).

Ви застосовуєте до отриманої перестановки $p$ дану ітерацію, поки вона не стане тотожною перестановкою (тобто рівною $(1, 2, 3, \dots, n))$ (1, 2, 3, \ldots, n)). Скільки часу це займе? Оскільки це число може бути дуже великим, виведіть його за модулем $1 0^{9} + 7$ 10^9+7.

Перестановка $p$ вважається лексикографічно меншою за перестановку $q$ , якщо існує такий індекс $i$ , що $p_{j} = q_{j}$ p_j = q_j для всіх $j < i$ j<i, а також $p_{i} < q_{i}$ p_i<q_i.

Input

Перший рядок містить єдине число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2\cdot 10^5) — довжину перестановки.

Другий рядок містить $n$ цілих чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n ( $1 \leq p_{i} \leq n$ 1 \le p_i \le n, всі числа попарно різні) — елементи перестановки.

Output

Виведіть кількість секунд, яка пройде, поки процес не завершиться, за модулем $1 0^{9} + 7$ 10^9+7.

Examples

Example 1

Example 2

Note

В першому прикладі маємо:

$(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2)$ (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, 3, 4, 2) \to (1, 3, 2, 4): $1$ секунда.

$(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3)$ (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, 2, 4, 3) \to (1, 2, 3, 4): $1$ секунда.

Всього $6$ секунд.