class Solution {

    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        if (len <= 2) {
            return 1;
        }
        int[] dp = new int[len+1];
        for (int i = 2; i<=len;i++){
            dp[i] = Math.min(dp[i-2]+cost[i-2],dp[i-1+cost[i-1]]);
        }
        return dp[len];
    }
}

class Solution {

    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        if (len <= 2) {
            return 1;
        }
        int pre_pre = 0,pre=0;
        for (int i = 2; i<=len;i++){
            int cur  = Math.min(pre_pre+cost[i-2],pre+cost[i-1]);
            pre_pre = pre;
            pre = cur;
        }
        return pre;
    }
}

//dp[i][j]: the longest palindromic subsequence's length of substring(i, j), here i, j represent left, right indexes in the string
//State transition:
// dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
// otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
// Initialization: dp[i][i] = 1
class Solution {

    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int[][] dp = new int[len][len];

        //in order to get next step, we need to know: dp[i+1][j-1],dp[i+1][j], dp[i][j-1].
        //so we should iterate from tail to head for i, and i to tail for j.
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else {
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}

// dp[i][j] means the biggest number of stones you can get more than opponent picking piles in piles[i] ~ piles[j].
// You can first pick piles[i] or piles[j].

// If you pick piles[i], your result will be piles[i] - dp[i + 1][j]
// If you pick piles[j], your result will be piles[j] - dp[i][j - 1]
// So we get:
// dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
class Solution {

    public boolean stoneGame(int[] piles) {
        if (piles == null || piles.length <= 2) {
            return true;
        }
        int len = piles.length;
        int[][] dp = new int[len][len];

        for (int i = len - 2; i >= 0; i--) {
            dp[i][i] = piles[i];
            for (int j = i + 1; j < len; j++) {
                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][len - 1] > 0;
    }
}

return true;

class Solution {

    public int findLength(int[] A, int[] B) {
        int lenA = A.length;
        int lenB = B.length;

        //dp[i][j] is the length of longest common subarray ending with nums[i-1] and nums[j-1]
        //[a,b,c, F] [a,b,c, D] -> dp[3][3] = 3 dp[4][4] = 0
        int[][] dp = new int[lenA + 1][lenB + 1];

        int max = 0;
        for(int i = 1;i<=lenA;i++){
            for(int j = 1 ;j<=lenB;j++){
                if(A[i-1]==B[j-1]  ){
                    dp[i][j] = dp[i-1][j-1]+1;
                    max = Math.max(max,dp[i][j]);
                }
            }
        }

        return max;
    }
}

class Solution {

    String s;
    String p;
    HashMap<String, Boolean> map;

    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        map = new HashMap<>();
        return dp(0,0);
    }

    public boolean dp(int i, int j) {
        String pos = i + "," + j;
        if (map.containsKey(pos)) {
            return map.get(pos);
        }
        if(j==p.length()){
            return i == s.length();
        }

        boolean firstMatched = i<s.length() && (p.charAt(j)==s.charAt(i) || p.charAt(j)=='.');

        boolean res;
        if(j + 1 < p.length() && p.charAt(j+1)=='*') {
            res = dp(i,j+2) || (firstMatched && dp(i+1,j));
        }else{
            res = firstMatched && dp(i+1,j+1);
        }
        
        map.put(pos,res);
        return res;

    }
}

class Solution {

    Map<String, Integer> map;
    List<Integer> price;
    List<List<Integer>> special;

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int size = price.size();
        this.price = price;
        this.special = special;
        map = new HashMap<>();

        return dp(needs, 0);


    }

    //use idx to prevent case like:
    //offer1->offer2 && offer2->offer1
    private int dp(List<Integer> cart, int idx) {

        String pos = cart.toString();
        //already compute, just return.
        if (map.containsKey(pos)) {
            return map.get(pos);
        }
        //base case, worst choice is to buy it without offers.
        int res = directPurchase(cart);
        
        //iterate through all the offers.
        for (int offerIdx = idx; offerIdx < special.size(); offerIdx++) {
            List<Integer> offer = special.get(offerIdx);
            List<Integer> temp = new ArrayList<>();
            //skip if the offer is invalid
            for (int i = 0; i < cart.size(); i++) {
                if (cart.get(i) - offer.get(i) < 0) {
                    temp = null;
                    break;
                }
                temp.add(cart.get(i) - offer.get(i));
            }
            if (temp == null) {
                continue;
            }
            //find min prices
            //use offerIdx to prevent idx: 1->2->1
            //you can still use the same offer for several times.
            res = Math.min(res, dp(temp, offerIdx) + offer.get(offer.size() - 1));
        }

        map.put(pos, res);
        return res;
    }

    private int directPurchase(List<Integer> needs) {
        int total = 0;
        for (int i = 0; i < needs.size(); i++) {
            total += price.get(i) * needs.get(i);
        }

        return total;
    }
}

//iterate through all the days, the min value for 1 -> today will be either dp[i-1] with 1-day, dp[i-7] plus a 7-day or dp[i-30] plus a 30-day
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[30];
        int travelIdx = 0;
        int val_cur = 0;
        for (int d = 1; d <= 365; d++) {
            //if today is not a travel day, the fae are the same as yesterday.
            if (d != days[travelIdx]) {
                dp[d % 30] = dp[(d - 1 + 30) % 30];
                continue;
            }

            travelIdx++;
            val_cur = Math
                .min(
                    dp[(d - 1 + 30) % 30] + costs[0], Math.min(
                        dp[(Math.max(d - 7, 0) + 30) % 30] + costs[1], 
                        dp[(Math.max(0, d - 30) + 30) % 30] + costs[2]
                    ));

            //early stop, already finish the travel.
            if (travelIdx == days.length) {
                break;
            }

            dp[d % 30] = val_cur;
        }
        
        return val_cur;
    }
}

//main idea is as Robbing House, take it or skip the current one will lead to diff res.
class Solution {
    public int deleteAndEarn(int[] nums) {
        HashMap<Integer, Integer> bucket = new HashMap<>();
        int len = 0;
        for (int num : nums) {
            bucket.put(num, bucket.getOrDefault(num, 0) + num);
            len = Math.max(len, num);
        }

        int take = 0;
        int skip = 0;

        for (int i = 1; i <= len; i++) {
            int pre_take = take;
            //if take it, then previous one should not be taken.
            take = skip + bucket.getOrDefault(i, 0);

            //if skip, find the max for taking or skipping the previous one.
            skip = Math.max(pre_take, skip);
        }
        return Math.max(take, skip);
    }
}

//instead of adding from "", can try to delete every character from the longest one.
//go from the shorest one, calc it and store in the memo.
//so the next string can try to delete one of the char and get max length from the prev.
class Solution {

    public int longestStrChain(String[] words) {
        HashMap<String, Integer> map = new HashMap();
        int res = 1;
        Arrays.sort(words, (a, b) -> (a.length() - b.length()));
        for (String word : words) {
            int len = word.length();
            int localBest = -1;
            for (int i = 0; i < len; i++) {
                String prev = word.substring(0, i) + word.substring(i + 1);
                localBest = Math.max(localBest, map.getOrDefault(prev, 0) + 1);
            }
            map.put(word, localBest);
            res = Math.max(res, localBest);
        }
        return res;
    }
}

class Solution {

    public int minimumDeleteSum(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();

        int[][] dp = new int[len1 + 1][len2 + 1];

        //need to init the base base, "" and "xxx" will have cost sum(ACS(X)).
        for (int j = 1; j <= len2; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }

        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + (int) s1.charAt(i - 1), dp[i][j - 1] + (int) s2.charAt(j - 1));
                }
            }
        }
        return dp[len1][len2];
    }
}

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums==null || nums.length==0){
            return res;
        }
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        //base case
        dp[0] = 0;

        int max_pos = 0;
        for(int i = 1;i<nums.length;i++){
            //iterate through all the prev and count the most subarray.
            for(int j = i-1;j>=0;j--){
                if(nums[i]%nums[j]==0){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            //if it's the largrest subarray so far.
            if(dp[i]>dp[max_pos]){
                max_pos = i;
            }
        }

        int prev = nums[max_pos];
        int cur_level = dp[max_pos];

        //go back from the largest number of the subarray.
        for(int i = max_pos;i>=0;i--){
            //need to check level to make sure it's the prev of the largest number.
            if(prev % nums[i]==0 && dp[i]==cur_level){
                res.add(nums[i]);
                prev = nums[i];
                cur_level--;
            }
        }

        return res;

    }
}

class Solution {
    public int findLongestChain(int[][] pairs) {
        if(pairs==null || pairs.length==0){
            return 0;
        }
        int len = pairs.length;
        Arrays.sort(pairs,(a,b)->(a[0]-b[0]));

        int[] dp = new int[len+1];
        int res = 0;
        for(int i = 1;i<=len;i++){
            dp[i] = 1;
            for(int j = i-1;j>=1;j--){
                if(pairs[i-1][0]>pairs[j-1][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

class Solution {

    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) {
            return 0;
        }
        int len = pairs.length;
        Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));

        int[] cur = pairs[0];

        int res = 1;
        for (int i = 1; i < len; i++) {
            if (pairs[i][0] > cur[1]) {
                cur = pairs[i];
                res++;
            }

        }
        return res;
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;

        int i;
        for (i = 0; fast.next != null; i++)//Get the total length 
        {
            fast = fast.next;
        }

        for (int j = i - n % i; j > 0; j--) //Get the i-n%i th node
        {
            slow = slow.next;
        }

        fast.next = dummy.next; //Do the rotation
        dummy.next = slow.next;
        slow.next = null;

        return dummy.next;
    }
}

//4 -> 4 -> 10 -> 10 -> 10 -> 15 -> 15 -> 24 -> 24
//0 -> 9 ->  9 ->  9 -> 12 -> 12 -> 20 -> 20 -> 20
//5 -> 5 ->  5 -> 18 -> 18 -> 18 -> 18 -> 18 -> 22

//As merge K sort, use priorityQueue to find the next min value
//try to find the min range.
//until both of the array reach the end.
class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        if (nums == null || nums.size() == 0) {
            return null;
        }

        int size = nums.size();
        //sort by value and min value at the top.
        PriorityQueue<Element> pq = new PriorityQueue<>(size, (a, b) -> (a.val - b.val));

        int cur_max = Integer.MIN_VALUE;
        int gap = Integer.MAX_VALUE;
        int[] res = new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};

        //push first elements of all list.
        //find the cur_max of the heap.
        for (int row = 0; row < size; row++) {
            Element e = new Element(nums.get(row).get(0), row, 0);
            pq.offer(e);
            cur_max = Math.max(cur_max, e.val);
        }

        //if pq is smaller than size of the arrays, means at least one of the arrays will not be in the range.
        while (pq.size() == size) {
            Element cur_element = pq.poll();
            //if the range is smaller, update.
            if (cur_max - cur_element.val < gap) {
                res[0] = cur_element.val;
                res[1] = cur_max;
                gap = cur_max - cur_element.val;
            }

            //if it has next value.
            if (cur_element.idx + 1 < nums.get(cur_element.row).size()) {
                cur_element.idx++;
                cur_element.val = nums.get(cur_element.row).get(cur_element.idx);
                pq.offer(cur_element);
                //update the max of the heap.
                cur_max = Math.max(cur_max, cur_element.val);
            }
        }

        return res;
    }

    class Element {
        int val;
        int row;
        int idx;

        public Element(int val, int row, int idx) {
            this.val = val;
            this.row = row;
            this.idx = idx;
        }
    }
}

class Solution {
    static final int busket = 2;

    public int totalFruit(int[] tree) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int res = 0;
        for (int i = 0, j = 0; j < tree.length; j++) {
            count.put(tree[j], count.getOrDefault(tree[j], 0) + 1);
            while (count.size() > 2) {
                //tree[i] must in the map since all nodes are iterate before the current one so the number will always >= 0.
                count.put(tree[i], count.get(tree[i]) - 1);
                if (count.get(tree[i]) == 0) {
                    count.remove(tree[i]);
                }
                i++;
            }
            res = Math.max(res, j - i + 1);
        }

        return res;
    }
}

class Solution {
    public int[] sortedSquares(int[] A) {
        int len = A.length;
        int i = 0, j = len - 1;
        int[] res = new int[len];
        for (int idx = len - 1; idx >= 0; idx--) {
            if (Math.abs(A[i]) > Math.abs(A[j])) {
                res[idx] = A[i] * A[i];
                i++;
            } else {
                res[idx] = A[j] * A[j];
                j--;
            }
        }
        return res;
    }
}

//get the idea from histogram.
class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack();
        int i = 0;
        int count = 0;
        //keep stack non-ascending.
        while(i<height.length){
            //stack is empty or equal to prev.
            if(stack.isEmpty() || height[stack.peek()]>=height[i]){
                stack.push(i++);
            }else{
                //the bottom
                int bottom = height[stack.pop()];
                //if the stack is empty after pop, means reached the boarder, cannot contain water.
                //if the stack is not, find the min of either boarders, minus the bottom, 
                //multiple the length between two boarders.
                int vol = stack.isEmpty()?0:(
                        (Math.min(height[stack.peek()],height[i]) - bottom) * (i-stack.peek()-1)
                        );
                count += vol;
            }
        }
        
        return count;
    }
}

class MinStack {

    Node head;
    /** initialize your data structure here. */
    public MinStack() {
        head = null;
    }

    public void push(int x) {
        if(head == null){
            head = new Node(x,x);
        }else{
            //head will be the most current one.
            head = new Node(x,Math.min(x,head.min),head);
        }
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        if(head==null){
            throw new EmptyStackException();
        }else{
            return head.val;
        }
    }

    public int getMin() {
        if(head==null){
            throw new EmptyStackException();
        }else{
            return head.min;
        }
    }

    class Node{
        int val;
        int min;
        Node next;

        public Node(int val, int min){
            this.val = val;
            this.min = min;
        }

        public Node(int val, int min, Node next){
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

/**
 * 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[] dailyTemperatures(int[] T) {
        //keep stack descending
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            //while peek is lower than the current temp, means today is the first warmer day.
            while(!stack.isEmpty() && T[i]>T[stack.peek()]){
                int prev = stack.pop();
                //gap between two days.
                res[prev] = i - prev;
            }
            stack.push(i);
        }
        return res;
    }
}

// Given the string s, the greedy choice (i.e., the leftmost letter in the answer) is the smallest s[i], s.t.
// the suffix s[i .. ] contains all the unique letters. (Note that, when there are more than one smallest s[i]'s
//we choose the leftmost one. Why? Simply consider the example: "abcacb".)

// After determining the greedy choice s[i], we get a new string s' from s by

// removing all letters to the left of s[i],
// removing all s[i]'s from s.
class Solution {
    public String removeDuplicateLetters(String s) {
        if(s==null || s.isEmpty()){
            return "";
        }
        int[] count = new int[26];
        for(char c : s.toCharArray()){
            count[c-'a']++;
        }

        int pos = 0;
        for(int i = 0;i<s.length();i++){
            if(s.charAt(pos)>s.charAt(i)){
                pos = i;
            }
            if(--count[s.charAt(i)-'a']==0){
                break;
            }
        }

        String next = s.substring(pos+1);
        next = next.replaceAll(""+s.charAt(pos),"");
        return "" + s.charAt(pos) + removeDuplicateLetters(next);
    }
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {

    Stack<NestedInteger> stack = new Stack();

    public NestedIterator(List<NestedInteger> nestedList) {
        pushNext(nestedList);
    }

    private void pushNext(List<NestedInteger> nestedList){
        //push to stack backward so can iterate forward.
        for(int i = nestedList.size()-1;i>=0;i--){
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        //run hasNext() will come to two result:
        //1. stack.peek() is an Integer
        //2. stack is empty
        if(!hasNext()){
            return null;
        }
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        //will go deep until reach an integer.
       while(!stack.isEmpty() && !stack.peek().isInteger()){
           List<NestedInteger> list = stack.pop().getList();
           pushNext(list);
       }
       return !stack.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        
        while(cur != null || !stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            res.add(cur.val);
            cur = cur.right;
        }
        return res;
    }
}

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> pre = new LinkedList<Integer>();
        if(root==null) return pre;
        pre.add(root.val);
        pre.addAll(preorderTraversal(root.left));
        pre.addAll(preorderTraversal(root.right));
        return pre;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> pre = new LinkedList<Integer>();
        preHelper(root,pre);
        return pre;
    }
    public void preHelper(TreeNode root, List<Integer> pre) {
        if(root==null) return;
        pre.add(root.val);
        preHelper(root.left,pre);
        preHelper(root.right,pre);
    }

class Solution {
    public List<Integer> preorderIt(TreeNode root) {
        List<Integer> pre = new LinkedList<Integer>();
        if(root==null) return pre;
        Stack<TreeNode> tovisit = new Stack<TreeNode>();
        tovisit.push(root);
        while(!tovisit.empty()) {
            TreeNode visiting = tovisit.pop();
            pre.add(visiting.val);
            if(visiting.right!=null) tovisit.push(visiting.right);
            if(visiting.left!=null) tovisit.push(visiting.left);
        }
        return pre;
    }
}

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.add(p.val);  // Add before going to children
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            p = node.right;   
        }
    }
    return result;
}

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            p = p.left;
        } else {
            TreeNode node = stack.pop();
            result.add(node.val);  // Add after all left children
            p = node.right;   
        }
    }
    return result;
}

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

class Solution {
    public int scoreOfParentheses(String S) {
        Deque<Integer> stack  = new ArrayDeque();
        int res = 0;
        for(char par : S.toCharArray()){
            if(par == '('){
                stack.push(res);
                res = 0;
            }else{
                res = res==0?1:2*res;
                res += stack.pop();
            }
        }
        return res;
    }
}

class Solution {
    public int sumSubarrayMins(int[] A) {
      // initialize previous less element and next less element of 
      // each element in the array
        
        Stack<int[]> previousLess = new Stack<>();
        Stack<int[]> nextLess = new Stack<>();
        int[] leftDistance = new int[A.length];
        int[] rightDistance = new int[A.length];
        
        for(int i=0; i<A.length; i++)
        {
            // use ">=" to deal with duplicate elements
            while(!previousLess.isEmpty() && previousLess.peek()[0] >= A[i])
            {
                previousLess.pop();
            }
            
            leftDistance[i] = previousLess.isEmpty() ? i+1 : i - previousLess.peek()[1];
            previousLess.push(new int[]{A[i], i});
            
        }
        
        for(int i=A.length-1; i>=0; i--)
        {
            while(!nextLess.isEmpty() && nextLess.peek()[0] > A[i])
            {
                nextLess.pop();
            }
            
            rightDistance[i] = nextLess.isEmpty() ? A.length - i : nextLess.peek()[1] - i;
            nextLess.push(new int[]{A[i], i});
        } 
        
        int ans = 0;
        int mod = 1000000007;
        for(int i=0; i<A.length; i++)
        {
            ans = (ans + A[i] * leftDistance[i] * rightDistance[i]) % mod;
        }
        return ans;
    }
}

class Solution {
    public int calPoints(String[] ops) {
        int sum = 0;
        Deque<Integer> stack = new ArrayDeque();
        
        for(String score : ops){
            if("+".equals(score)){
                int pre = stack.pop();
                int localSum = pre+ stack.peek();
                stack.push(pre);
                stack.push(localSum);
                sum += localSum;
            }else if("D".equals(score)){
                sum += 2 * stack.peek();
                stack.push(2*stack.peek());
            }else if("C".equals(score)){
                sum -= stack.peek();
                stack.pop();
            }else{
                int num = Integer.parseInt(score);
                sum += num;
                stack.push(num);
            }
                
        }
        return sum;
    }
}

import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        
        if(queue1.isEmpty()){
            queue1.offer(x);
            while(!queue2.isEmpty()){
                queue1.offer(queue2.poll());
            }
        }else{
            queue2.offer(x);
            while(!queue1.isEmpty()){
                queue2.offer(queue1.poll());
            }
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if(!queue1.isEmpty()){
            return queue1.poll();
        }else{
            return queue2.poll();
        }
    }

    /**
     * Get the top element.
     */
    public int top() {
        if(!queue1.isEmpty()){
            return queue1.peek();
        }else{
            return queue2.peek();
        }
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

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

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        helper(res,"",0,0,n);
        return res;
    }

    public void helper(List<String> res, String temp, int open, int close, int n){
        if(temp.length() == 2*n){
            res.add(temp);
            return;
        }
        if(open < n){
            helper(res,temp+"(",open+1,close,n);
        }
        //close can not exceed open or will be invalid.
        if(close < open){
            helper(res,temp+")",open,close+1,n);
        }
    }
}

class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        helper(new ArrayList<>(), nums, res);
        return res;
    }

    private void helper(List<Integer> temp, int[] nums, List<List<Integer>> res) {
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (temp.contains(nums[i])) {
                continue;
            }

            temp.add(nums[i]);
            helper(temp, nums, res);
            temp.remove(temp.size() - 1);
        }
    }
}

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        helper(candidates,target,0,0,new ArrayList<>(),res);
        return res;
    }

    private void helper(int[] candidates, int target, int idx, int tempSum,List<Integer> temp, List<List<Integer>> res){

        if(tempSum >= target){
            if(tempSum == target){
            	//DEEP CLONE! otherwise will be removed and be empty.
                res.add(new ArrayList<>(temp));
            }
            return;
        }

        //start from idx, so i itself can be duplicated, but will not track backward.
        //prevent case like [2,2,3] and [2,3,2]
        for(int i = idx;i<candidates.length;i++){
            temp.add(candidates[i]);
            helper(candidates,target,i,tempSum+candidates[i],temp,res);
            temp.remove(temp.size()-1);
        }
    }

}

public class Solution {

    public boolean exist(char[][] board, String word) {
    	//loop over to pick every possible start.
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (exist(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean exist(char[][] board, int i, int j, String word, int ind) {
        if (ind == word.length()) {
            return true;
        }
        //if the current idx is not the same, just go bacl, no need to go further.
        if (i > board.length - 1 || i < 0 || j < 0 || j > board[0].length - 1 || board[i][j] != word.charAt(ind)) {
            return false;
        }

        //remove the current board[i][j] to prevent duplicate backward.
        board[i][j] = '*';

        boolean result =
            exist(board, i - 1, j, word, ind + 1) ||
            exist(board, i, j - 1, word, ind + 1) ||
            exist(board, i, j + 1, word, ind + 1) ||
            exist(board, i + 1, j, word, ind + 1);

        //revert it for others to visit.
        board[i][j] = word.charAt(ind);
        return result;
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        res.add(temp);
        helper(res,temp,nums,0);
        return res;
    }

    public void helper(List<List<Integer>> res, List<Integer> temp,int[] nums, int idx){
        if(idx >= nums.length){
            return;
        }
        for(int i = idx;i<nums.length;i++){
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            helper(res,temp,nums,i+1);
            temp.remove(temp.size()-1);
        }
    }
}

import java.util.ArrayList;
import java.util.List;

class Solution {

    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        helper(s,0,res,"");
        return res;
    }

    public void helper(String s,  int count, List<String> res, String temp) {
        if (count == 4 || s.length()==0) {
            if(count == 4 && s.length()==0){
            	//first '.' will be removed.
                res.add(temp.substring(1));
            }
            return;
        }

        for (int i = 1; i <= s.length() && i <= (s.charAt(0) == '0'?1:3); i++) {
            int val = Integer.parseInt(s.substring(0,i));
            if (val <= 255) {
            	//use substring to prevent use idx.
                 helper(s.substring(i),count+1,res,temp+"."+val);

            }
        }
    }
}

class Solution {

    public List<List<String>> partition(String s) {
        List<String> temp = new ArrayList<>();
        List<List<String>> res = new ArrayList<>();
        helper(s,res,temp,0);
        return res;
    }

    public void helper(String s, List<List<String>> res, List<String> temp, int left) {
        if (left >= s.length() && temp.size() != 0) {
            res.add(new ArrayList<>(temp));
            return;
        }

        for (int i = left; i < s.length(); i++) {
            if(isPalindrome(s,left,i)){
                if(i==left){
                    temp.add(""+s.charAt(i));
                }else{
                    temp.add(s.substring(left,i+1));
                }
                helper(s,res,temp,i+1);
                temp.remove(temp.size()-1);
            }
            
        }

    }

    private boolean isPalindrome(String str, int l, int r) {
        if (l == r) {
            return true;
        }
        while (l < r) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        helper(res,1,temp,n,k);
        return res;
    }

    public void helper(List<List<Integer>> res, int idx, List<Integer> temp, int n, int k) {
        if (k == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }

        //pruning, stop beforehead.
        //since there's k item to be added, there's no point to start after n-k+1 which will never satisitied.
        for (int i = idx; i <= n-k+1 ;i++) {
            temp.add(i);
            helper(res,i+1,temp,n,k-1);
            temp.remove(temp.size()-1);
        }
    }
}