URI Online Judge | 1088

Burbujas y Baldes

Por Cláudio L. Lucchesi  Brazil

Límite de Tiempo: 3

Andrea, Carlos y Marcelo son amigos muy cercanos y pasan los fines de semana en la piscina. Mientras Andrea se está bronceando, sus amigos juegan Burbujas. Andrea, una científica en computación muy inteligente, les ha dicho a ellos que no entiende porque pasan tanto tiempo jugando un juego tan simple.

Usando su computadora, Carlos y Marcelo generan un numero entero aleatorio N y una secuencia, también aleatoria, la cual es una permutación desde 1, 2, ..., N.

Luego el juego comienza. Los jugadores juegan por turnos, y en cada turno un jugador hace un movimiento. Marcelo es siempre el primero en jugar. Un movimiento consiste en escoger un par de elementos consecutivos que están fuera del orden en la secuencia, e intercambiarlos a ambos. Por ejemplo, dada la secuencia 1, 5, 3, 4, 2, un jugador puede intercambiar 3 y 5 o 4 y 2, pero no puede intercambiar 3 y 4 o 5 y 2. Continuando con el ejemplo, si el jugador decide intercambiar 5 y 3, la nueva secuencia será 1, 3, 5, 4, 2.

Tarde o temprano, la secuencia estará ordenada. El jugador que no puede hacer un movimiento pierde. Andrea, con desdén, siempre dice que sería más simple jugar Par o Impar, con el mismo efecto. Tu misión, en caso que decidas aceptarla, es determinar quién gana el juego, dada la permutación inicial P.

Entrada

La entrada contiene varios casos de prueba. Cada caso de prueba está compuesto por una sola línea, en la cual todos los enteros están separados por un solo espacio. Cada línea contiene un entero N (2 ≤ N ≤ 105), seguido por la secuencia inicial P = (X1, X2, ...,XN) de N enteros distintos, con 1 ≤ Xi ≤ N para 1 ≤ i ≤ N.

El final de la entrada es indicado por una línea conteniendo solamente un cero.

Salida

Para cada caso de prueba en la entrada, tu programa debe imprimir una sola línea, conteniendo el nombre del ganador, igual a Carlos o Marcelo.

Ejemplo de entrada Ejemplo de salida

5 1 5 3 4 2
5 5 1 3 4 2
5 1 2 3 4 5
6 3 5 2 1 4 6
5 5 4 3 2 1
6 6 5 4 3 2 1
0

Marcelo
Carlos
Carlos
Carlos
Carlos
Marcelo