Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) B题（博弈）

B. Conan and Agasa play a Card Game

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 ai written on it.

They 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 aj < ai.

A 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.

Input

The first line contains an integer n (1 ≤ n ≤ 105) — the number of cards Conan has.

The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105), where ai is the number on the i-th card.

Output

If Conan wins, print "Conan" (without quotes), otherwise print "Agasa" (without quotes).

    Examples  
      input    
3
4 5 7
      output    
Conan
      input    
2
1 1
      output    
Agasa

Note

In 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.

In 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.

题意：有一些牌，牌上面写着数字，Conan（以下简称C）和Agasa（以下简称A）两人玩游戏，每个人轮流取走任意一张牌和比它小的所有牌，最后谁取走最后一张牌，谁赢。

要求预测游戏结果，结果必须是两个人发挥最好的情况。

分析：由于是两个人轮流取，且C先取，那么C肯定要制定自己赢的方式，可以想到，如果最大的数只出现一次的话，那么C一次可以取走。两次呢？如果他还是取最大值的话，由于最大值只能取走一个，所以另一个肯定留给了A，题目要求C和A都是智商很高的人，所以C不会这么做。三次呢？假设还是取最大值，那么会剩下两个刚才是最大值的相同数字，那么A肯定只能拿走一个，最后一个留给了C，初步想结论，最大值的数量是奇数的话，C肯定会赢。

那么A什么时候赢呢？最大值是偶数？非也！

我们假设最大值是偶数，前面说了这种情况C肯定不会取最大值，那就分析一下第二大的值。

第二大的值的数量如果是奇数的话，这里用一个简单的例子说明

1 1 2 2 3 3 4 4 4 5 5

当C取走4的时候，桌面上剩下 4 4 5 5 ，这时A有两种选择（假设A在分析），如果我选4，那么假设C选4，毫无疑问，他肯定会拿最后一个5，所以C肯定会赢（因为C是聪明人！这里要反复强调题目描述里最后一句话。）所以当C第一次取走4的时候已经决定他是赢家了。

如果有3个3呢？一样，如果C拿4或者5必输。这时会拿3，334455，A无论拿任何一个数都会输，最简单的情况，A拿3，C肯定拿3.然后就是上面的情况。

如果3个3和3个4呢？那跟11223344455是一样的。

结论：存在某一个数，出现奇数次，C肯定能赢。

那么什么时候C必输也就是A赢呢？我们尝试把上面的结论做一个命题的否定。

任意一个数都出现偶数次。我们试一下，这时C尝试任何一个选择。1 1 2 2 3 3 4 4 5 5

取5和4的情况和上面一样（因为拿这个数就得去掉所有比它小的数）

取3的时候A肯定拿3，跟上边C一样拿4和5必输。最后可得无论C取任何数都是A赢。

所以可得解。分析时要注意：只要某个人存在能赢的情况，他就肯定能赢。我看了题解才想到这一点，做题的时候想的很复杂很复杂，推出一个奇数个奇数C才赢……最后把自己绕进去了……所以做题的时候一定要抓住题的关键！

队里大牛跟我说这个是博弈，我一想，大师们下象棋的时候，肯定会考虑很多步，也肯定会让自己赢，道理都是差不多的。

不多说，下面给出代码：

/* ***********************************************
Author        :Boqian Lv
Created Time  :2018/1/30 21:59:34
File Name     :cf458b.cpp
************************************************ */

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int a0,t;
	cin>>a0;
	int a[100010];
	memset(a,0,sizeof(a));
	for(int i=0;i<a0;i++)
	{
		cin>>t;
		a[t]++;
	}
	int cnt=0,flag=0;
	for(int i=100000;i>=1;i--)
	{
		if(a[i]!=0)
		{
			if(a[i]%2)
			{
				cnt++;
			}
		}
	}
	if(cnt)cout<<"Conan"<<endl;
	else cout<<"Agasa"<<endl;

    return 0;
}