Secuencias completamente desordenadas#9882
Recientemente le han nombrado investigador científico principal de la NASA — la Asociación Nacional de Algoritmos de Ordenamiento (National Association for Sorting Algorithms). ¡Felicidades! Su principal responsabilidad es probar los algoritmos de ordenamiento que desarrolla su equipo. Afortunadamente, este año la NASA cuenta con un gran presupuesto, y ha logrado adquirir los números enteros más modernos para probar los algoritmos de ordenamiento.
Como investigador científico principal, usted sabe perfectamente que los algoritmos se evalúan por su comportamiento en los datos de entrada más desfavorables. Por eso, para probar los algoritmos de ordenamiento necesita secuencias que estén lo más desordenadas posible.
Sea dada una secuencia de números (a_1, \ldots, a_n). Diremos que el elemento a_k está en su lugar si a_j \ge a_k para todos los índices j > k y a_j \le a_k para todos los índices j < k. Por ejemplo, en la secuencia
están en su lugar los elementos , la segunda aparición de y . Observe que la secuencia está ordenada si y solo si todos sus elementos están en su lugar. Una secuencia se llama completamente desordenada si ninguno de sus elementos está en su lugar.
¿Cuántas secuencias completamente desordenadas se pueden obtener permutando los elementos de una secuencia dada de números enteros? Dos secuencias (b_1, \ldots, b_n) y (c_1, \ldots, c_n) se consideran distintas si b_i \ne c_i para algún índice i \in \{1, \ldots, n\}. Dado que este número puede ser muy grande, muéstrelo módulo 10^9 + 9.
En la primera línea se da un número entero n~(1 \le n \le 5000).
En la segunda línea se dan números enteros a_1, \ldots, a_n~(0 \le a_i \le 10^9).
Muestre un único número entero — la cantidad de secuencias completamente desordenadas que se pueden obtener permutando los elementos de a_1, \ldots, a_n, módulo 10^9 + 9.
Ejemplo 1
Ejemplo 2
Ejemplo 3