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

    public int countPaths(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        long[][] cache = new long[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(matrix, i, j, cache);
            }
        }
        long ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans += cache[i][j];
            }
        }
        return (int) (ans % (mod));

    }

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

    private boolean isOutOfBound(int rowLength, int colLength, int row, int col) {
        return row < 0 || row >= rowLength || col < 0 || col >= colLength;
    }
}

class Solution {
    private static class Pair {
        int time;
        String web;

        Pair(int _time, String _web) {
            time = _time;
            web = _web;
        }
    }

    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
        Map<String, List<Pair>> userPair = new HashMap<>();
        for (int i = 0; i < username.length; i++) {
            userPair.putIfAbsent(username[i], new ArrayList<>());
            userPair.get(username[i]).add(new Pair(timestamp[i], website[i]));
        }
        String res = "";
        Map<String, Integer> patternCount = new HashMap<>();
        for (String user : userPair.keySet()) {
            List<Pair> pairList = userPair.get(user);
            Collections.sort(pairList, (a, b) -> a.time - b.time);
            Set<String> patterns = new HashSet<>();
            for (int i = 0; i < pairList.size(); i++) {
                for (int j = i + 1; j < pairList.size(); j++) {
                    for (int k = j + 1; k < pairList.size(); k++) {
                        StringBuilder currPattern = new StringBuilder();
                        currPattern.append(pairList.get(i).web)
                                .append(" ")
                                .append(pairList.get(j).web)
                                .append(" ")
                                .append(pairList.get(k).web);
                        String currPatternString = currPattern.toString();
                        if (patterns.add(currPatternString)) {
                            patternCount.put(currPatternString, patternCount.getOrDefault(currPatternString, 0) + 1);
                            if (res.equals("") || patternCount.get(res) < patternCount.get(currPatternString)
                                    || (patternCount.get(res) == patternCount.get(currPatternString)
                                            && res.compareTo(currPatternString) > 0)) {
                                res = currPatternString;
                            }
                        }
                    }
                }
            }
        }
        return Arrays.asList(res.split(" "));
    }
}

class Program {
    public int[] dijkstrasAlgorithm(int start, int[][][] edges) {
        int numberOfVertex = edges.length;

        int[] minDistances = new int[numberOfVertex];
        Arrays.fill(minDistances, Integer.MAX_VALUE);
        minDistances[start] = 0;

        Set<Integer> visited = new HashSet<Integer>();

        while (visited.size() != numberOfVertex) {
            int[] currentVertexData = getVertexWithMinDistances(minDistances, visited);
            int currentVertexIdx = currentVertexData[0];
            int currentVertexDistanceToStart = currentVertexData[1];

            if (currentVertexDistanceToStart == Integer.MAX_VALUE) {
                break;
            }

            visited.add(currentVertexIdx);

            // 来看从当前位置到自己所有neighors的距离是不是更近
            for (int[] edge : edges[currentVertexIdx]) {
                int destination = edge[0];
                int distanceToDestination = edge[1];

                // 之间就visit过(作为我们研究的对象, 把周围的neighbor都遍历了一遍并更新minDistance这个数组)
                if (visited.contains(destination)) {
                    continue;
                }

                // 未被visited过的node可能从之前我们研究的某个node也能到达那里, 但是先到的不一定就更近
                // 当然也有之前没有去过的node. 我们看看从当前的位置到周围的neighbor是不是更近
                int newPathToDestinationDistance = currentVertexDistanceToStart + distanceToDestination;
                if (newPathToDestinationDistance < minDistances[destination]) {
                    minDistances[destination] = newPathToDestinationDistance;
                }
            }
        }

        int[] finalDistances = new int[numberOfVertex];
        for (int i = 0; i < numberOfVertex; i++) {
            finalDistances[i] = minDistances[i] == Integer.MAX_VALUE ? -1 : minDistances[i];
        }
        return finalDistances;
    }

    public int[] getVertexWithMinDistances(int[] minDistances, Set<Integer> visited) {
        int vertex = -1;
        int currentMinDistance = Integer.MAX_VALUE;

        for (int vertexIdx = 0; vertexIdx < minDistances.length; vertexIdx++) {
            if (visited.contains(vertexIdx)) {
                continue;
            }
            int currentDistance = minDistances[vertexIdx];
            if (currentDistance <= currentMinDistance) {
                vertex = vertexIdx;
                currentMinDistance = currentDistance;
            }
        }

        return new int[] { vertex, currentMinDistance };
    }
}

class Program {
    public static List<Integer> topologicalSort(List<Integer> jobs, List<Integer[]> deps) {
        Map<Integer, Integer> dependencyNum = new HashMap<>();
        Map<Integer, List<Integer>> dependents = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        for (Integer[] dep : deps) {
            if (!dependents.containsKey(dep[0])) {
                dependents.put(dep[0], new ArrayList<>());
            }
            dependents.get(dep[0]).add(dep[1]);
            dependencyNum.put(dep[1], dependencyNum.getOrDefault(dep[1], 0) + 1);
        }
        for (int i = 0; i < jobs.size(); i++) {
            if (!dependencyNum.containsKey(jobs.get(i))) {
                q.offer(jobs.get(i));
            }
        }
        while (!q.isEmpty()) {
            int currentJob = q.poll();
            result.add(currentJob);
            List<Integer> currentJobDependents = dependents.get(currentJob);
            if (currentJobDependents != null) {
                for (Integer job : currentJobDependents) {
                    dependencyNum.put(job, dependencyNum.get(job) - 1);
                    if (dependencyNum.get(job) == 0) {
                        q.offer(job);
                        dependencyNum.remove(job);
                    }
                }
            }
        }
        return dependencyNum.isEmpty() ? result : new ArrayList<Integer>();
    }
}

class Solution {
    public long minimumHealth(int[] damage, int armor) {
        long sum = 0;
        long max = -1;
        for (int num : damage) {
            max = Math.max(max, num);
            sum += num;
        }
        if (armor >= max) {
            sum -= max;
        } else {
            sum -= armor;
        }
        return sum + 1;
    }
}

class Solution {
    public long subArrayRanges(int[] nums) {
        List<Integer> list = new ArrayList<>();
        list.add(Integer.MIN_VALUE);
        for (int num : nums) {
            list.add(num);
        }
        list.add(Integer.MIN_VALUE);
        Deque<Integer> stack = new ArrayDeque<>();
        long ans = 0;
        for (int i = 0; i < list.size(); i++) {
            while (!stack.isEmpty() && list.get(i) < list.get(stack.peek())) {
                int currIdx = stack.pop();
                ans -= 1L * list.get(currIdx) * (currIdx - stack.peek()) * (i - currIdx);
            }
            stack.push(i);
        }
        stack.clear();
        list.set(0, Integer.MAX_VALUE);
        list.set(list.size() - 1, Integer.MAX_VALUE);
        for (int i = 0; i < list.size(); i++) {
            while (!stack.isEmpty() && list.get(i) > list.get(stack.peek())) {
                int currIdx = stack.pop();
                ans += 1L * list.get(currIdx) * (currIdx - stack.peek()) * (i - currIdx);
            }
            stack.push(i);
        }
        return ans;
    }
}

class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (a, b) -> (b[1] - a[1]));
        int ans = 0, remaining = truckSize;
        for (int i = 0; i < boxTypes.length && remaining > 0; i++) {
            if (boxTypes[i][0] <= remaining) {
                ans += boxTypes[i][0] * boxTypes[i][1];
                remaining -= boxTypes[i][0];
            } else {
                ans += remaining * boxTypes[i][1];
                remaining = 0;
            }
        }
        return ans;
    }
}

class Solution {
    public int getMaxLen(int[] nums) {
        int lastZero = -1, firstNegative = -1, sum = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                lastZero = i;
                firstNegative = -1;
                sum = 0;
                continue;
            }
            if (nums[i] < 0) {
                firstNegative = firstNegative == -1 ? i : firstNegative;
                sum += 1;
            }
            if (sum % 2 == 0) {
                ans = Math.max(ans, i - lastZero);
            } else {
                ans = Math.max(ans, i - firstNegative);
            }
        }
        return ans;
    }
}

class Solution {
    public int largestUniqueNumber(int[] nums) {
        int max = -1;
        Arrays.sort(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                return nums[i];
            }
            while (i > 0 && nums[i] == nums[i - 1]) {
                i -= 1;
            }
        }
        return -1;
    }
}

class Solution {
    public int brokenCalc(int startValue, int target) {
        int steps = 0;
        while (target > startValue) {
            if (target % 2 == 1) {
                target += 1;
            } else {
                target /= 2;
            }
            steps += 1;
        }
        return steps + startValue - target;
    }
}