class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
        // index means the length of the chain and the element means the last pair's 1st
        // element
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < pairs.length; i++) {
            int targetChainIdx = binarySearch(list, pairs[i][0]);
            if (targetChainIdx + 1 == list.size()) {
                list.add(pairs[i][1]);
            } else {
                list.set(targetChainIdx + 1, Math.min(list.get(targetChainIdx + 1), pairs[i][1]));
            }
        }
        return list.size();
    }

    private int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size() - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.left != null && root.right == null) {
                root = root.left;
            } else if (root.left == null && root.right != null) {
                root = root.right;
            } else {
                TreeNode predecessor = findPredecessor(root);
                root.val = predecessor.val;
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }

    private TreeNode findPredecessor(TreeNode node) {
        node = node.left;
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }
}

class Logger {
    private Deque<Pair<Integer, String>> q;
    private Set<String> occurred;
    private String emptyString;

    public Logger() {
        q = new ArrayDeque<>();
        occurred = new HashSet<>();
        emptyString = "";
    }

    public boolean shouldPrintMessage(int timestamp, String message) {
        int expirationTime = timestamp - 10;
        while (!q.isEmpty() && q.peek().getKey() <= expirationTime) {
            occurred.remove(q.poll().getValue());
        }
        if (occurred.contains(message)) {
            return false;
        } else {
            q.offer(new Pair<>(timestamp, message));
            occurred.add(message);
            return true;
        }
    }
}

class Solution {
    private int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int longestIncreasingPath(int[][] matrix) {
        int[][] cache = new int[matrix.length][matrix[0].length];
        int max = -1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                max = Math.max(max, dfs(matrix, i, j, cache));
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int row, int col, int[][] cache) {
        if (cache[row][col] != 0) {
            return cache[row][col];
        }
        int maxLength = 1;
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutOfBound(matrix, newRow, newCol) && matrix[row][col] < matrix[newRow][newCol]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, newRow, newCol, cache));
            }
        }
        cache[row][col] = maxLength;
        return cache[row][col];
    }

    private boolean isOutOfBound(int[][] matrix, int row, int col) {
        return row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length;
    }
}

class Solution {
    private TreeNode lastVisited = null, x = null, y = null;

    public void recoverTree(TreeNode root) {
        dfs(root);
        swap(x, y);
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (lastVisited != null && root.val < lastVisited.val) {
            y = root;
            if (x == null) {
                x = lastVisited;
            } else {
                return;
            }
        }
        lastVisited = root;
        dfs(root.right);
    }

    private void swap(TreeNode nodeOne, TreeNode nodeTwo) {
        int temp = nodeOne.val;
        nodeOne.val = nodeTwo.val;
        nodeTwo.val = temp;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        int nextPlace = 1, ptr = 1, count = 1;
        while (ptr < nums.length) {
            if (nums[ptr] != nums[ptr - 1]) {
                count = 1;
                nums[nextPlace] = nums[ptr];
                nextPlace += 1;
            } else if (nums[ptr] == nums[ptr - 1] && count < 2) {
                nums[nextPlace] = nums[ptr];
                count += 1;
                nextPlace += 1;
            }
            ptr += 1;
        }
        return nextPlace;
    }
}

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

    private void helper(List<List<Integer>> ans, List<Integer> curr, int pos, int n, int k) {
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = pos; i <= n; i++) {
            curr.add(i);
            helper(ans, curr, i + 1, n, k);
            curr.remove(curr.size() - 1);
        }
    }
}

class Solution {
    public int[][] generateMatrix(int n) {
        int totalNum = n * n;
        int count = 1;
        int[][] ans = new int[n][n];
        int left = 0, right = n - 1, up = 0, down = n - 1;
        while (count <= totalNum) {
            for (int i = left; i <= right; i++) {
                ans[up][i] = count++;
            }
            for (int i = up + 1; i <= down; i++) {
                ans[i][right] = count++;
            }
            for (int i = right - 1; i >= left && count <= totalNum; i--) {
                ans[down][i] = count++;
            }
            for (int i = down - 1; i > up && count <= totalNum; i--) {
                ans[i][left] = count++;
            }
            left += 1;
            right -= 1;
            up += 1;
            down -= 1;
        }
        return ans;
    }
}

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        // (timestamp, scores)
        TreeMap<Integer, Integer> timeScoresMap = new TreeMap<>();
        for (List<Interval> intervals : schedule) {
            for (Interval interval : intervals) {
                timeScoresMap.put(interval.start, timeScoresMap.getOrDefault(interval.start, 0) + 1);
                timeScoresMap.put(interval.end, timeScoresMap.getOrDefault(interval.end, 0) - 1);
            }
        }

        int start = -1, scores = 0;
        List<Interval> ans = new ArrayList<>();
        for (int time : timeScoresMap.keySet()) {
            scores += timeScoresMap.get(time);
            if (scores == 0 && start == -1) {
                start = time;
            } else if (scores > 0 && start != -1) {
                ans.add(new Interval(start, time));
                start = -1;
            }
        }
        return ans;

    }
}

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int mod = 1000000007;
        int[] newArr = new int[arr.length + 2];
        newArr[0] = Integer.MIN_VALUE;
        for (int i = 1; i <= arr.length; i++) {
            newArr[i] = arr[i - 1];
        }
        newArr[newArr.length - 1] = Integer.MIN_VALUE;
        Deque<Integer> monoStack = new ArrayDeque<>();
        long ans = 0;
        for (int i = 0; i < newArr.length; i++) {
            while (!monoStack.isEmpty() && newArr[i] < newArr[monoStack.peek()]) {
                int currIdx = monoStack.pop();
                ans += 1L * newArr[currIdx] * (i - currIdx) * (currIdx - monoStack.peek());
            }
            monoStack.push(i);
        }
        return (int) (ans % mod);
    }
}