#include <stdio.h>

int x[] = { 1, 1, 3, 4, 3, 1, 3, 1, 2, 2, 1, 1, 1, 6, 0, 1 };

int vitez(int *x, int N)	// Vrací vítěze nebo $-1$, není\li
{
  int l=0, r=N-1;		// Levý a pravý okraj zpracovávaného úseku
  int m=N/2;			// Mez výhry
  int z;			// Hodnota, podle níž rozdělujeme
  int i, j, k;			// Pomocné proměnné

  while (r-l >= m)		// Dokud je ještě šance
    {
      z = 0;			// Předprůchod
      j = x[l];
      for(i=l; i<=r; i++)
        {
          z += x[i];
          if (x[i] != j) j = -1;
        }
      if (j >= 0)		// Všechny stejné $\Rightarrow$ vítěz.
        return j;
      z /= r-l+1;		// $z$ je aritmetický průměr
      i = l;			// A rozdělujeme\dots
      j = r;
      while (i < j)
        {
          while (i <= j && x[i] <= z)
            i++;
          while (i <= j && x[j] > z)
            j--;
          if (i < j)
            { k=x[i]; x[i]=x[j]; x[j]=k; }
        }
      if (j-l > r-i)		// Pokračujeme větším z~úseků
        r = j;			// \dots\ levým
      else
        l = i;			// \dots\ pravým
    }
  return -1;			// Smůla\dots
}

void main(void)
{
  printf("%d\n", vitez(x, sizeof(x)/sizeof(int)));
}