class Solution {
public:
    int fib(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        int* dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
};

class CQueue {
public:
        stack<int> s1;
        stack<int> s2;
    CQueue() {
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        int len1=s1.size();
        if(len1==0)
            return -1;
        for(int i=0;i<len1;i++)
        {
            if(i==len1-1)
            {
                int temp=s1.top();
                s1.pop();
                while(s2.size())
                {
                    s1.push(s2.top());
                    s2.pop();
                }
                return temp;
            }
            s2.push(s1.top());
            s1.pop();
        }
        return -1;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<int> v(100005,0);

        for(int i=0;i<nums.size();i++)
        {
            if(v[nums[i]]!=0)
            {
                return nums[i];
            }
            v[nums[i]]++;
        }
        return nums[0];
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int len = nums.size();
        int candidate = -1;
        int count = 0;

        for(int i=0;i<len;i++)
        {
            if(count==0)
            {
                candidate=nums[i];
            }
            if(nums[i]==candidate)
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        int count2=0;
        for(int i=0;i<len;i++)
        {
            if(nums[i]==candidate)
                count2++;
        }

        if(count2*2>len)
        {
            return candidate;
        }
        else
        {
            return -1;
        }
    }
};