Napravimo ternarno stablo na sledeći način. Napravimo po jedan list za savku poziciju u početnom redu. Zatim uzimajmo prva 3 čvora iz reda i napravimo novi čvor koji će biti njihov direktni predak. Ubacimo novi čvor na kraj reda. To ponavljamo sve dok ne ostane samo jedan čvor u redu i on je koren stabla. Ako bismo u listove upisali nivoe veštine takmičara i u svaki čvor upisali medijanu brojeva njegovih direktnih potomaka u korenu bismo dobili nivo veštine pobednika.

Problem ćemo dalje rešavati binarnom pretragom po vrednosti rešenja. Recimo da proveravamo da li je rešenje barem $X$. Da bi u nekom čvoru imali broj veći ili jednak $X$, bar 2 njegova direktna potmoka moraju imati brojeve veće ili jednake $X$. Dinamičkim programiranjem na stablu ćemo odrediti koliko najmanje brojeva većih ili jednakih $X$ treba da stavimo u prazne listove kako bi u korenu stabla bio broj veći ili jednak $X$. Neka je $dp(node)$ ova vrednost ako posmatramo samo podstablo čvora $node$. Za prazne listove $dp(node)=1$. Za listove u koje je već upisan broj veći ili jednak $X$, $dp(node)=0$, a ako je uisan broj manji od $X$, $dp(node)= + \infty$. Za ostale čvorove ovu vrednost računamo po formuli $dp(node)=dp(ch1)+dp(ch2)$ gde su $ch1$, $ch2$ i $ch3$ direktni potomci čvora $node$ i $dp(ch1) \leq dp(ch2) \leq dp(ch3)$. Ako je $dp(root)$ manje ili jednako broju takmičara koji nisu poranili i imaju $A_i \geq X$, rešenje je veće ili jednako $X$.

Vremenska složenost: $O(Nlog(max A_i))$

Zadatak je preuzet sa $\texttt{JOI}$ $\texttt{Final}$ $\texttt{Round}$ $\texttt{2015}$.