#include <iostream>
using namespace std;
 
int majorityElement(int nums[], int n) {
    int count = 0, candidate = 0;
 
    for (int i = 0; i < n; i++) {
        if (count == 0)
            candidate = nums[i];
 
        if (nums[i] == candidate)
            count++;
        else
            count--;
    }
    return candidate;
}
 
int main() {
    int nums[] = {2,2,1,1,1,2,2};
    int n = 7;
    cout << majorityElement(nums, n);
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1ham9yaXR5RWxlbWVudChpbnQgbnVtc1tdLCBpbnQgbikgewogICAgaW50IGNvdW50ID0gMCwgY2FuZGlkYXRlID0gMDsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGlmIChjb3VudCA9PSAwKQogICAgICAgICAgICBjYW5kaWRhdGUgPSBudW1zW2ldOwoKICAgICAgICBpZiAobnVtc1tpXSA9PSBjYW5kaWRhdGUpCiAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgZWxzZQogICAgICAgICAgICBjb3VudC0tOwogICAgfQogICAgcmV0dXJuIGNhbmRpZGF0ZTsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgbnVtc1tdID0gezIsMiwxLDEsMSwyLDJ9OwogICAgaW50IG4gPSA3OwogICAgY291dCA8PCBtYWpvcml0eUVsZW1lbnQobnVtcywgbik7CiAgICByZXR1cm4gMDsKfQ==