만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

버블 게임의 승자

시간 제한2초메모리 제한512 MB

요약
인접한 역순 쌍을 번갈아 바꾸어 수열을 정렬하고, 더 이상 바꿀 쌍이 없는 사람이 지는 게임에서 승자를 판정한다.
난이도

보통10점 중 5점

유형
조합론, 게임 이론, 수학
정답자
아직 제출이 없습니다

문제

Andrea와 Carlos, Marcelo는 주말마다 수영장에서 함께 시간을 보낸다. Andrea가 햇볕을 쬐는 동안 나머지 두 사람은 버블이라는 놀이를 한다. 컴퓨터과학을 공부하는 Andrea는 이렇게 단순한 놀이에 왜 그렇게 오래 매달리는지 모르겠다고 말한다.

두 사람은 Andrea의 노트북으로 임의의 정수 NN과 1,2,…,N1, 2, \dots, N의 임의의 순열을 하나 만든다.

두 사람은 한 번씩 번갈아 수를 두고, 항상 Marcelo가 먼저 시작한다.

한 번의 수는 수열에서 순서가 뒤바뀐 인접한 두 원소를 골라 서로 자리를 바꾸는 것이다. 예를 들어 수열이 1,5,3,4,21, 5, 3, 4, 2이면 5와 3의 자리를 바꿀 수 있고 4와 2의 자리를 바꿀 수도 있지만, 3과 4는 바꿀 수 없고 5와 2도 바꿀 수 없다. 여기서 5와 3을 바꾸면 수열은 1,3,5,4,21, 3, 5, 4, 2가 된다.

언젠가는 수열이 오름차순으로 정렬된다. 자기 차례에 둘 수 있는 수가 없는 사람이 진다.

Andrea는 동전을 던져도 결과는 똑같다고 시큰둥하게 말한다. 처음 수열이 주어질 때 누가 이기는지 판정하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 주어지고, 정수는 공백 하나로 구분된다. 각 줄은 정수 NN (2≤N≤1052 \le N \le 10^5)으로 시작하고, 이어서 처음 수열 P=(X1,X2,…,XN)P = (X_1, X_2, \dots, X_N)을 이루는 서로 다른 정수 NN개가 온다. 모든 ii에 대해 1≤Xi≤N1 \le X_i \le N이다.

입력의 마지막 줄에는 00 하나만 주어진다.

출력

각 테스트 케이스마다 이긴 사람의 이름을 한 줄에 출력한다. 이름은 Carlos 또는 Marcelo이고, 여분의 공백 없이 그대로 출력한다.

예제1

  1. 예제 1

    입력
    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