{"problem":{"name":"B. Conan and Agasa play a Card Game","description":{"content":"Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has _n_ cards, and the _i_\\-th card has a number _a__i_ written on ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF914B"},"statements":[{"statement_type":"Markdown","content":"Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has _n_ cards, and the _i_\\-th card has a number _a__i_ written on it.\n\nThey take turns playing, starting with Conan. In each turn, the player chooses a card and removes it. Also, he removes all cards having a number strictly lesser than the number on the chosen card. Formally, if the player chooses the _i_\\-th card, he removes that card and removes the _j_\\-th card for all _j_ such that _a__j_ < _a__i_.\n\nA player loses if he cannot make a move on his turn, that is, he loses if there are no cards left. Predict the outcome of the game, assuming both players play optimally.\n\n## Input\n\nThe first line contains an integer _n_ (1 ≤ _n_ ≤ 105) — the number of cards Conan has.\n\nThe next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105), where _a__i_ is the number on the _i_\\-th card.\n\n## Output\n\nIf Conan wins, print \"_Conan_\" (without quotes), otherwise print \"_Agasa_\" (without quotes).\n\n[samples]\n\n## Note\n\nIn the first example, Conan can just choose the card having number 7 on it and hence remove all the cards. After that, there are no cards left on Agasa's turn.\n\nIn the second example, no matter which card Conan chooses, there will be one one card left, which Agasa can choose. After that, there are no cards left when it becomes Conan's turn again.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"江户川柯南厌倦了破案，于是邀请了他的朋友阿笠博士来玩牌。柯南有 #cf_span[n] 张牌，第 #cf_span[i] 张牌上写着数字 #cf_span[ai]。\n\n他们轮流出牌，由柯南先手。每轮中，玩家选择一张牌并将其移除，同时移除所有数字严格小于所选牌数字的牌。形式上，如果玩家选择第 #cf_span[i] 张牌，他会移除这张牌，以及所有满足 #cf_span[aj < ai] 的第 #cf_span[j] 张牌。\n\n如果一名玩家在自己的回合无法出牌（即没有牌剩下），则他输掉游戏。假设双方都采取最优策略，请预测游戏的结果。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 柯南拥有的牌数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 105])，其中 #cf_span[ai] 是第 #cf_span[i] 张牌上的数字。\n\n如果柯南获胜，请输出 \"_Conan_\"（不含引号），否则输出 \"_Agasa_\"（不含引号）。\n\n在第一个例子中，柯南只需选择数字为 #cf_span[7] 的牌，从而移除所有牌。之后，阿笠博士回合时已无牌可选。\n\n在第二个例子中，无论柯南选择哪张牌，都会剩下一张牌，阿笠博士可以选走它。之后，当轮到柯南再次出牌时，已无牌可选。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 柯南拥有的牌数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 105])，其中 #cf_span[ai] 是第 #cf_span[i] 张牌上的数字。\n\n## Output\n\n如果柯南获胜，请输出 \"_Conan_\"（不含引号），否则输出 \"_Agasa_\"（不含引号）。\n\n[samples]\n\n## Note\n\n在第一个例子中，柯南只需选择数字为 #cf_span[7] 的牌，从而移除所有牌。之后，阿笠博士回合时已无牌可选。在第二个例子中，无论柯南选择哪张牌，都会剩下一张牌，阿笠博士可以选走它。之后，当轮到柯南再次出牌时，已无牌可选。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ a_1, a_2, \\dots, a_n $ be the multiset of numbers on the cards.\n\nDefine the **maximum value** $ m = \\max_{1 \\le i \\le n} a_i $, and let $ c $ be the **count** of cards with value $ m $.\n\nThe game is equivalent to a variant of Nim where only the cards with the maximum value matter, because:\n\n- Choosing any card with value $ v < m $ leaves at least one card with value $ m $, which the opponent can then choose to remove all remaining cards.\n- Choosing a card with value $ m $ removes **all** cards (since all other values are $ \\le m $, and only those strictly less are removed — so all cards with value $ m $ remain? Wait: correction).\n\n**Clarification of move effect:**\nWhen a player chooses a card with value $ a_i $, they remove:\n- The chosen card,\n- All cards with value $ < a_i $.\n\nCards with value $ \\ge a_i $ **remain**, except the chosen one.\n\nThus, if a player picks a card with value $ m $, they remove:\n- That card,\n- All cards with value $ < m $.\n\nSo all cards with value $ m $ **except the chosen one** remain.\n\nTherefore, if there are $ c $ cards with value $ m $, and a player picks one of them, then $ c - 1 $ cards with value $ m $ remain, and all smaller cards are gone.\n\nThe game reduces to: players alternately remove **one** card from the set of cards with value $ m $, and the player who takes the **last** such card wins? Not exactly.\n\nActually, the game ends when **no cards remain**. So the player who takes the **last card** wins (because the next player cannot move).\n\nBut note: when you pick a card with value $ m $, you remove **only** that one card and all cards strictly less than $ m $. So if there are $ c $ cards of value $ m $, and you pick one, you remove **one** card of value $ m $ and all smaller cards — so the remaining cards are the other $ c - 1 $ cards of value $ m $.\n\nSo the game becomes: there are $ c $ identical \"high-value\" cards (all equal to $ m $), and on each turn, a player removes **exactly one** of them (and all smaller cards, which are already gone after first such move). So the game is equivalent to a pile of $ c $ stones, where each move removes one stone. Players alternate, and the player who takes the last stone wins.\n\nThus, this is equivalent to a Nim heap of size $ c $.\n\n- If $ c $ is **odd**, the first player (Conan) wins.\n- If $ c $ is **even**, the second player (Agasa) wins.\n\n**Why?** Because once the first player picks a card with value $ m $, all smaller cards vanish. The rest of the game only involves the remaining $ c - 1 $ cards of value $ m $, and each move removes exactly one such card. So it's a simple subtraction game of size $ c $, first player wins iff $ c $ is odd.\n\n**Conclusion:**\n\nLet $ m = \\max(a_i) $, and $ c = \\#\\{ i : a_i = m \\} $.\n\n- If $ c $ is odd → Conan wins.\n- If $ c $ is even → Agasa wins.\n\n---\n\n**Formal Statement:**\n\nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{N}^n $, $ n \\ge 1 $, $ a_i \\ge 1 $.\n\nDefine:\n- $ m = \\max_{1 \\le i \\le n} a_i $,\n- $ c = \\left| \\left\\{ i \\in \\{1, 2, \\dots, n\\} : a_i = m \\right\\} \\right| $.\n\nThen:\n$$\n\\text{Winner} =\n\\begin{cases}\n\\text{Conan} & \\text{if } c \\text{ is odd}, \\\\\n\\text{Agasa} & \\text{if } c \\text{ is even}.\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF914B","tags":["games","greedy","implementation"],"sample_group":[["3\n4 5 7","Conan"],["2\n1 1","Agasa"]],"created_at":"2026-03-03 11:00:39"}}