/ Binary Search
class Solution_BS {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int left = 0, right = t.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (t[mid] >= nums[i]) right = mid;
                else left = mid + 1;
            }
            res[i] = right;
            t.insert(t.begin() + right, nums[i]);
        }
        return res;
    }
    int takeMost(vector<int> nums){
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size()));
        for(int len=1; len<=nums.size(); len++){
            for(int i=0; i+len-1<=nums.size()-1; i++){
                int j = i+len-1;
                if(j-i==0){
                    dp[j][i] = nums[i];
                }else if(j-i==1){
                    dp[j][i] = max(nums[j], nums[i]);
                }else{
                    dp[j][i] = max( nums[i]+ (nums[i+1]>nums[j]? dp[j][i+2]:dp[j-1][i+1]), nums[j]+ (nums[i]>nums[j-1]? dp[j-1][i+1]:dp[j-2][i]) );
                }
            }
        }
     }

    int applyOp(char op, int b, int a)
    {
        switch (op)
        {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        }
        return 0;
    }

void updateStack(stack<int>& operands, stack<char>& operators){
    if(!operators.empty() && operators.top() != '('){

        int num2 = operands.top(); operands.pop();
        int num1 = operands.top(); operands.pop();
        char op = operators.top(); operators.pop();
        int value = applyOp(op, num2, num1);
        operands.push(value);
    }
}