using System;
 
public class Test
{
	public static void Main()
	{
		// your code goes here
	}
}

dXNpbmcgU3lzdGVtOwoKcHVibGljIGNsYXNzIFRlc3QKewoJcHVibGljIHN0YXRpYyB2b2lkIE1haW4oKQoJewoJCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCX0KfQ==

ICAgIHB1YmxpYyBpbnQgTWFqb3JpdHlFbGVtZW50KGludFtdIG51bXMpCiAgICB7CiAgICAgICAgaW50IGNhbmRpZGF0ZSA9IDA7CiAgICAgICAgaW50IGNvdW50ID0gMDsKCiAgICAgICAgZm9yZWFjaCAoaW50IG51bSBpbiBudW1zKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGNvdW50ID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGNhbmRpZGF0ZSA9IG51bTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgY291bnQgKz0gKG51bSA9PSBjYW5kaWRhdGUpID8gMSA6IC0xOwogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGNhbmRpZGF0ZTsKICAgIH0KCiAgICBzdGF0aWMgdm9pZCBNYWluKCkKICAgIHsKICAgICAgICBpbnRbXSBudW1zID0geyAyLCAyLCAxLCAxLCAxLCAyLCAyIH07CgogICAgICAgIFNvbHV0aW9uIHMgPSBuZXcgU29sdXRpb24oKTsKICAgICAgICBDb25zb2xlLldyaXRlTGluZSgmcXVvdDtNYWpvcml0eSBFbGVtZW50ID0gJnF1b3Q7ICsgcy5NYWpvcml0eUVsZW1lbnQobnVtcykpOwogICAgfQ==

    public int MajorityElement(int[] nums)
    {
        int candidate = 0;
        int count = 0;

        foreach (int num in nums)
        {
            if (count == 0)
            {
                candidate = num;
            }

            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    static void Main()
    {
        int[] nums = { 2, 2, 1, 1, 1, 2, 2 };

        Solution s = new Solution();
        Console.WriteLine("Majority Element = " + s.MajorityElement(nums));
    }