G - Monedas ordenadas

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, Kotlin, C#
Time & Memory limits: (details)

Dos amigos están jugando con $N$ monedas en una fila dividida en casillas. Cada moneda tiene un número distinto escrito en ella. Los identificadores de las monedas van desde $1$ hasta $N$. Al inicio del juego ambos ponen las monedas de forma ordenada en algunas de las casillas de la fila. Después ambos jugadores van turnándose alternadamente hasta que no puedan hacer más movimientos. En un turno un jugador selecciona una moneda y la mueve hacia la izquierda al menos una casilla. Después de cada movimiento las monedas deben quedar ordenadas y ser todas visibles. Esto quiere decir que una moneda no puede pasar por encima de otra ni ser puesta en una casilla ocupada. El primer jugador que no puede hacer ningún movimiento pierde. Los dos amigos son muy buenos jugadores y siempre van a seguir la mejor estrategia para intentar ganar. Si sabemos dónde está cada moneda al inicio queremos predecir quién gana el juego.

Input

La primera línea de la entrada consiste en un número entero $N (1 \le N \le 10 ^ 4)$ que indica la cantidad de monedas en el juego. La próxima línea consiste en $N$ enteros positivos $m_i$ separados por un espacio, siendo $m_i (1 \le m_i \le 10 ^ 5)$ la posición de la moneda $i$. La primera casilla de la izquierda tiene posición $1$.

Output

Si el primer jugador siempre puede ganar entonces debe imprimir su primera jugada. Si hay varias jugadas que le permiten ganar se debe imprimir la que mueve menos casillas una moneda. Si aun así hay varias se debe escoger entonces la que mueve la moneda con menor número. El formato de la jugada es “Mueve $A$ casillas la moneda $B$.”, donde $A$ es la cantidad de casillas que se mueve la moneda a la izquierda y $B$ es su número. Si el primer jugador no puede ganar sin importar su jugada respuesta debe ser “Gana el segundo jugador.”

Sample test(s)

Input
2 1 5
Output
Mueve 3 casillas la moneda 2.
Input
2 2 3
Output
Gana el segundo jugador.