elemmaj

// Problema rezolvata pe Tutoriale-Pe.NET
// Citeste toata explicatia aici: http://tutoriale-pe.net/ro/elementul-majoritar-elmaj/

#include    <iostream>

using namespace std;

const int LIM = 1000005;

int N;
int V[LIM];

void Read()
{
    cin >> N;

    // Citim vectorul normal
    for(int i = 0; i < N; i++)
        cin >> V[i];

    // Declaram variabilele descrise mai sus
    int contor = 0, candidat = 0, aparitii = 0;

    // Parcurgem vectorul
    for(int i = 0; i < N; i++)
    {
        // Atunci cand contorul este 0, alegem elementul curent ca fiind candidatul
        // si setam contorul pe "1"
        if(contor == 0)
        {
            candidat = V[i];
            contor = 1;
        }
        else
        {
            // Daca avem deja contorul pornit, verificam elementul curent si adaugam +1
            // daca este acelasi nr ca si candidatul, si scadem -1 in caz contrar
            if(V[i] == candidat)
                contor += 1;
            else
                contor -= 1;
        }
    }

    // Mai parcurgem o data vectorul pentru a numara de cate ori apare candidatul
    for(int i = 0; i < N; i++)
        if(V[i] == candidat)
            aparitii += 1;

    // Tratam cazul in care nu avem element majoritar
    /*if(aparitii < N / 2 + 1)
        cout << "nu exista";
    else//*/
        cout << candidat << " " << aparitii;
}

int main()
{
    Read();
    return 0;
}