using System;
using System.Collections.Generic;
 
public class Test
{
	static public void Main()
	{
	    var r = new Random();
		for (int i = 0; i < 12; i++)
		{
		    var n = r.Next(5, 10);
		    Console.WriteLine("N={0}", n);
		    var p = generate(n);
		    show(p);
		    var a = bruteforce(p);
		    var b = median(p);
		    Console.WriteLine("MoM={0} Med={1} Match={2}", a, b, a == b);
		    Console.WriteLine();
		}
	}
 
	static double median(int[] p)
	{
	    Array.Sort(p);
	    if (p.Length % 2 == 0)
	    {
	        var a = p[p.Length / 2];
	        var b = p[p.Length / 2 - 1];
	        return (a + b) / 2.0;
	    }
	    else
	    {
	        return p[p.Length / 2];
	    }
	}
 
	static double bruteforce(int[] p)
	{
	    var m = new List<double>();
	    for (int i = 0; i < p.Length; i++)
	    {
	        for (int j = i; j < p.Length; j++)
	        {
	            var t = new int[j - i + 1];
	            Array.Copy(p, i, t, 0, t.Length);
	            m.Add(median(t));
	        }
	    }
	    m.Sort();
	    if (m.Count % 2 == 0)
	    {
	        var a = m[m.Count / 2];
	        var b = m[m.Count / 2 - 1];
	        return (a + b) / 2.0;
	    }
	    else
	    {
	        return m[m.Count / 2];
	    }
	}
 
	static int seed = Environment.TickCount;
	static int[] generate(int n)
	{
	    var r = new Random(seed);
	    seed ^= r.Next();
	    var ret = new int[n];
	    for (int i = 0; i < n; i++)
	    {
	        ret[i] = r.Next(1, (int)1e3);
	    }
	    return ret;
	}
 
	static void show(int[] arr)
	{
	    foreach (int a in arr)
	    {
	        Console.Write("{0} ", a);
	    }
	    Console.WriteLine();
	}
}

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKCnB1YmxpYyBjbGFzcyBUZXN0CnsKCXN0YXRpYyBwdWJsaWMgdm9pZCBNYWluKCkKCXsKCSAgICB2YXIgciA9IG5ldyBSYW5kb20oKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IDEyOyBpKyspCgkJewoJCSAgICB2YXIgbiA9IHIuTmV4dCg1LCAxMCk7CgkJICAgIENvbnNvbGUuV3JpdGVMaW5lKCJOPXswfSIsIG4pOwoJCSAgICB2YXIgcCA9IGdlbmVyYXRlKG4pOwoJCSAgICBzaG93KHApOwoJCSAgICB2YXIgYSA9IGJydXRlZm9yY2UocCk7CgkJICAgIHZhciBiID0gbWVkaWFuKHApOwoJCSAgICBDb25zb2xlLldyaXRlTGluZSgiTW9NPXswfSBNZWQ9ezF9IE1hdGNoPXsyfSIsIGEsIGIsIGEgPT0gYik7CgkJICAgIENvbnNvbGUuV3JpdGVMaW5lKCk7CgkJfQoJfQoJCglzdGF0aWMgZG91YmxlIG1lZGlhbihpbnRbXSBwKQoJewoJICAgIEFycmF5LlNvcnQocCk7CgkgICAgaWYgKHAuTGVuZ3RoICUgMiA9PSAwKQoJICAgIHsKCSAgICAgICAgdmFyIGEgPSBwW3AuTGVuZ3RoIC8gMl07CgkgICAgICAgIHZhciBiID0gcFtwLkxlbmd0aCAvIDIgLSAxXTsKCSAgICAgICAgcmV0dXJuIChhICsgYikgLyAyLjA7CgkgICAgfQoJICAgIGVsc2UKCSAgICB7CgkgICAgICAgIHJldHVybiBwW3AuTGVuZ3RoIC8gMl07CgkgICAgfQoJfQoJCglzdGF0aWMgZG91YmxlIGJydXRlZm9yY2UoaW50W10gcCkKCXsKCSAgICB2YXIgbSA9IG5ldyBMaXN0PGRvdWJsZT4oKTsKCSAgICBmb3IgKGludCBpID0gMDsgaSA8IHAuTGVuZ3RoOyBpKyspCgkgICAgewoJICAgICAgICBmb3IgKGludCBqID0gaTsgaiA8IHAuTGVuZ3RoOyBqKyspCgkgICAgICAgIHsKCSAgICAgICAgICAgIHZhciB0ID0gbmV3IGludFtqIC0gaSArIDFdOwoJICAgICAgICAgICAgQXJyYXkuQ29weShwLCBpLCB0LCAwLCB0Lkxlbmd0aCk7CgkgICAgICAgICAgICBtLkFkZChtZWRpYW4odCkpOwoJICAgICAgICB9CgkgICAgfQoJICAgIG0uU29ydCgpOwoJICAgIGlmIChtLkNvdW50ICUgMiA9PSAwKQoJICAgIHsKCSAgICAgICAgdmFyIGEgPSBtW20uQ291bnQgLyAyXTsKCSAgICAgICAgdmFyIGIgPSBtW20uQ291bnQgLyAyIC0gMV07CgkgICAgICAgIHJldHVybiAoYSArIGIpIC8gMi4wOwoJICAgIH0KCSAgICBlbHNlCgkgICAgewoJICAgICAgICByZXR1cm4gbVttLkNvdW50IC8gMl07CgkgICAgfQoJfQoJCglzdGF0aWMgaW50IHNlZWQgPSBFbnZpcm9ubWVudC5UaWNrQ291bnQ7CglzdGF0aWMgaW50W10gZ2VuZXJhdGUoaW50IG4pCgl7CgkgICAgdmFyIHIgPSBuZXcgUmFuZG9tKHNlZWQpOwoJICAgIHNlZWQgXj0gci5OZXh0KCk7CgkgICAgdmFyIHJldCA9IG5ldyBpbnRbbl07CgkgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCgkgICAgewoJICAgICAgICByZXRbaV0gPSByLk5leHQoMSwgKGludCkxZTMpOwoJICAgIH0KCSAgICByZXR1cm4gcmV0OwoJfQoJCglzdGF0aWMgdm9pZCBzaG93KGludFtdIGFycikKCXsKCSAgICBmb3JlYWNoIChpbnQgYSBpbiBhcnIpCgkgICAgewoJICAgICAgICBDb25zb2xlLldyaXRlKCJ7MH0gIiwgYSk7CgkgICAgfQoJICAgIENvbnNvbGUuV3JpdGVMaW5lKCk7Cgl9Cn0=