const int MAXN = 100050;

int q[MAXN];
int qmin[MAXN];

class MinStack {
public:
    int itop;
    /** initialize your data structure here. */
    MinStack() {
        itop = 0;
    }

    void push(int x) {
        // 首先将x插入到栈
        q[itop] = x;

        // 检查是否为最小值
        if (itop == 0) qmin[itop] = x;
        else {
            if (x < qmin[itop - 1]) {
                qmin[itop] = x;
            } else {
                qmin[itop] = qmin[itop - 1];
            }
        }
        ++ itop;
    }

    void pop() {
        if (itop > 0) itop --;
    }

    int top() {
        return q[itop - 1];
    }

    int getMin() {
        return qmin[itop - 1];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int ans = 0;
        for (int i = 0; i < endTime.size(); ++i) {
            if (queryTime >= startTime[i] && queryTime <= endTime[i])
                ans ++;
        }
        return ans;
    }
};

class Solution {
public:
    inline int Is(char x)
    {
        if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u')
            return 1;
        return 0;
    }
    int maxVowels(string s, int k) {
        int l = 0, r = k - 1, ans = 0, cur = 0;
        for (l; l < k; ++l) {
            cur += Is(s[l]);
        }
        ans = cur;
        l = 0;
        while (r < s.length()) {
            cur -= Is(s[l ++]);
            cur += Is(s[++ r]);
            ans = max(cur, ans);
        }
        return ans;
    }
};

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int idx = 0;
        sentence = sentence +  " ";
        while (idx < sentence.length() && sentence[idx] == ' ') idx ++;
        string buff = "";
        int count = 0;
        for (;idx < sentence.length(); ++idx) {
            if (sentence[idx] != ' ')
                buff += sentence[idx];
            else {
                count ++;
                if (buff.length() >= searchWord.length()) 
                    if (buff.substr(0, searchWord.length()) == searchWord)
                        return count;
                buff = "";
            }
        }
        return -1;
    }
};

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        if (r == -1) return 0;
        while (l < r) {
            int mid = l + r >> 1;
            if (mid == nums[mid]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (nums[l] == l) return l + 1;
        return l;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int treeDepth(TreeNode* root) {
       if (!root) return 0;
       int ans = 1;
       queue<TreeNode*>buff;queue<TreeNode*>buff1;
       buff.push(root);
       while (!buff.empty()) {
           auto t = buff.front();
           if (t -> left) buff1.push(t -> left);
           if (t -> right) buff1.push(t -> right);
           buff.pop();
           if (buff.empty()) {
               buff = buff1;
               if (!buff1.empty()) {
                   buff = buff1;
                   ans ++;
               }
               while (!buff1.empty()) buff1.pop();
           }
       }
       return ans;
    }
};

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int len = nums.size();

        for (int i = 0; i < len; ++i) {
            if (nums[i] == i) return i;
        }
        return -1;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>>ans; ans.clear();
        if (!root) return ans;

        queue<TreeNode*>buff; buff.push(root);
        queue<TreeNode*>buff1;
        vector<int>rbuff; rbuff.clear();
        while (!buff.empty()) {
            auto t = buff.front();
            rbuff.push_back(t -> val);
            buff.pop();
            if (t -> left) buff1.push(t -> left);
            if (t -> right) buff1.push(t -> right);

            if (buff.empty()) {
                buff = buff1;
                while (!buff1.empty()) buff1.pop();
                if (rbuff.size()) ans.push_back(rbuff);
                rbuff.clear();
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printFromTopToBottom(TreeNode* root) {
        vector<int>ans; ans.clear();
        if (!root) return ans;
        queue<TreeNode*>buff;
        buff.push(root);
        while (!buff.empty()) {
            auto t = buff.front();
            ans.push_back(t -> val);
            buff.pop();
            if (t -> left) buff.push(t -> left);
            if (t -> right) buff.push(t -> right);
        }
        return ans;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *ans = new ListNode(0);
        ListNode *cur = ans;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1 -> val < l2 -> val) {
                cur -> next = l1; l1 = l1 -> next;
            } else {
                cur -> next = l2; l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        cur -> next = (l1 != NULL ? l1 : l2);
        return ans -> next;
    }  
};