using System;

public class Test
{
	public static bool HasMajorityElement(int[] a)
	{
		int candidate = 0;
		int count = 0;
		foreach (int i in a)
		{
			if (count == 0)
			{ 
				candidate = i;
				count = 1;
			}
			else 
			{
				count += candidate == i ? 1 : -1;
			}
		}
		count = 0;
		foreach (int i in a)
		{
			if (i == candidate) ++count;
		}
		return count > a.Length / 2;
	}

	public static void Main()
	{
		var a = new int[] { 5, 2, 1, 3, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
		a = new int[] { 5, 1, 3, 1, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
		a = new int[] { 5, 1, 1, 1, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
		a = new int[] { 1, 1, 1, 1, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
		a = new int[] { 0, 4, 3, 2, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
		a = new int[] { 0, 0, 0, 2, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
		a = new int[] { 1, 5, 5, 5, 1 };
		System.Console.WriteLine("HasMajorityElement(): {0}", HasMajorityElement(a));
	}
}