NewbieContest

def maj(l, next_n=-1, count=0):
    
    if next_n == -1:
        return maj(l, l[0], 0)

    # Si liste paire et premier element majoritaire, on le retourne sinon on retourne la même fonction sans le premier element
    if len(l) % 2 == 0:
        if 2*l.count(l[0]) == len(l):
            return l[0]
        else:
            return maj(l[1:])

    for k,n in enumerate(l):
        """
        L'idée c'est qu'on cherche un élément strictement majoritaire.
        Donc si on parcourt la liste élément par élément en créant une sorte de liste temporaire
        On regarde dans cette liste temporaire s'il y a un element en majorité, qu'on garde quand on augmente la liste
        S'il n'y a pas de majorité, ça veut dire qu'il faut qu'il y ait une majorité dans le reste de la liste.

        Pour le premier element, il est seul dans la liste, donc il est majoritaire, il y en a 1 de plus de le reste.
        Si on ajoute le deuxieme element
        -> Si c'est le même alors il est majoritaire avec une majorité de 2 de plus que le rest
        -> Si c'est pas le même alors il n'est pas majoritaire, et on réduit le décompte. Ici, le compte arrive à 0, et on rappelle la fonction avec le reste de la liste

        Et ainsi de suite.
        Si le compte arrive à zéro, alors on renvoie le reste de la liste et on prend le premier élément comme majoritaire car 
        de toute façon dans les éléments précédents, il n'y a pas de majorité absolue, donc ce qui compte, c'est la majorité absolue dans ce qui reste.

        Exemple :
        l=[1,2,1,3,2,1,1]

        On prend "1", qu'on considère majoritaire dans l[:1] avec count = 1
        Ensuite on prend 2, différent de la majorité actuelle donc count = 0 dans l[:2].
        Comme count = 0, on se fiche de l[:2] finalement, aucune majorité ne s'en dégage. Donc on veut un majorité dans l[2:]
        Donc on rappelle la fonction avec l[2:]

        Ca va etre rappelé avec [1,3,2,1,1] puis [2,1,1] puis [1] donc l'élément potentiellement majoritaire est 1. Il est vérifié dans get_maj
        """
        if count == 0:
            return maj(l[k:], n, 1)
        elif count != 0 and next_n == n:
            count += 1
        else:
            count -= 1
    if l.count(next_n)*2 >= len(l):
        return next_n
    else:
        return -1

"""
Quand on a un élément potentiel, on le compte, et on vérifie qu'il est bon
"""
def get_maj(l):
    if l.count(maj(l))*2 >= len(l):
        return maj(l)
    else:
        return -1

def maj(l):
    count = 0
    next_n = -1
    if len(l) % 2 == 0:
        if 2*l.count(l[0]) == len(l):
            return l[0]
        else:
            return maj(l[1:])

    for n in l:
        if count == 0:
            next_n, count = n, 1
        elif count != 0 and next_n == n:
            count += 1
        else:
            count -= 1
    if l.count(next_n)*2 >= len(l):
        return next_n
    else:
        return -1

#encoding=utf8
def maj2(liste):
    N = len(liste)
    if N==0:
        return -1
    cpt = 0
    for element in liste:
        if cpt == 0:
            candidat = element
        if candidat == element:
            cpt += 1
        else:            
            cpt -= 1
    
    #cas cpt > 0:
    #seule l'élément majoritaire de la dernière sous-séquence
    #peut être majoritaire globalement
    if cpt > 0:
        if liste.count(candidat)*2 >= N:
            return candidat
        return -1
    #cas cpt == 0:
    #la longueur de la liste est paire
    #il n'y a pas d'élément strictement majoritaire
    #il suffit de tester si le dernier candidat et le dernier élément
    #de la liste (qui sont différents) sont majoritaires
    count1 = liste.count(candidat)
    count2 = liste.count(liste[-1])
    if count1 == count2:
        return -1
    elif count1*2 >= N:
        return candidat
    elif count2*2 >= N:
        return liste[-1]
    return -1