Se te da una permutación (p_1, p_2, \ldots, p_n) de los números del al .
Puedes realizar la siguiente operación con ella:
Puedes intercambiar dos elementos adyacentes de . Esta operación toma exactamente un segundo.
En una iteración haces lo siguiente:
Considera la permutación (q_1, q_2, \ldots, q_n) que está inmediatamente antes de (p_1, p_2, \ldots, p_n) en orden lexicográfico, es decir, es lexicográficamente menor que y no existe ninguna permutación "entre ellas". Por ejemplo, para p = (2, 3, 1) tenemos q = (2, 1, 3), para p = (3, 1, 2, 4) tenemos q = (2, 4, 3, 1), y para p = (1, 4, 2, 3) tenemos q = (1, 3, 4, 2).
Transforma la permutación en la permutación usando la menor cantidad posible de operaciones. Por ejemplo, para transformar (1, 4, 2, 3) en (1, 3, 4, 2) se necesitan al menos operaciones: (1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2).
Aplicas esta iteración a la permutación resultante hasta que se convierta en la permutación identidad (es decir, igual a (1, 2, 3, \ldots, n)). ¿Cuánto tiempo tomará esto? Como este número puede ser muy grande, imprímelo módulo 10^9+7.
Una permutación se considera lexicográficamente menor que una permutación si existe un índice tal que p_j = q_j para todo j<i, y además p_i<q_i.
La primera línea contiene un entero (1 \le n \le 2\cdot 10^5) — la longitud de la permutación.
La segunda línea contiene enteros p_1, p_2, \ldots, p_n (1 \le p_i \le n, todos los números son distintos dos a dos) — los elementos de la permutación.
Imprime la cantidad de segundos que pasarán hasta que el proceso termine, módulo 10^9+7.
Ejemplo 1
Ejemplo 2
En el primer ejemplo tenemos:
(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2): segundos.
(1, 3, 4, 2) \to (1, 3, 2, 4): segundo.
(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3): segundos.
(1, 2, 4, 3) \to (1, 2, 3, 4): segundo.
En total, segundos.