class Solution {
    private int count;

    public int countArrangement(int n) {
        backtrack(1, n, new boolean[n + 1]);
        return count;
    }

    private void backtrack(int pos, int n, boolean[] visited) {
        if (pos > n) {
            count += 1;
            return;
        }
        for (int i = 1; i <= n; ++i) {
            if (!visited[i] && Math.max(i, pos) % Math.min(i, pos) == 0) {
                visited[i] = true;
                backtrack(pos + 1, n, visited);
                visited[i] = false;
            }
        }
    }
}

class Solution {
    private int deepest;
    private int ans;

    public int findBottomLeftValue(TreeNode root) {
        deepest = -1;
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
        if (node.left == null && node.right == null && depth > deepest) {
            ans = node.val;
            deepest = depth;
        }
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0, head), prev = dummy, ptr = head;
        while (ptr != null) {
            if (ptr.val == val) {
                prev.next = ptr.next;
                ptr.next = null;
                ptr = prev.next;
            } else {
                prev = ptr;
                ptr = ptr.next;
            }
        }
        return dummy.next;
    }
}

class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for (int i = nums.length - 3; i >= 0; i--) {
            if (nums[i] + nums[i + 1] > nums[i + 2]) {
                return nums[i] + nums[i + 1] + nums[i + 2];
            }
        }
        return 0;
    }
}

class Solution {
    public int hIndex(int[] citations) {
        int left = 1, right = citations.length, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[citations.length - mid] >= mid) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int left = 1, right = citations.length, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int ptr = 0;
            while (ptr < mid) {
                int currPaper = citations[citations.length - 1 - ptr];
                if (currPaper < mid) {
                    break;
                }
                ptr += 1;
            }
            if (ptr == mid && (ptr == citations.length || citations[citations.length - 1 - ptr] <= mid)) {
                ans = mid;
                left = mid + 1;
            } else if (ptr < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

class NumMatrix {
    private int[][] prefixSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefixSum = new int[m][n];
        for (int i = 0; i < m; i++) {
            int currRowSum = 0;
            for (int j = 0; j < n; j++) {
                currRowSum += matrix[i][j];
                prefixSum[i][j] += currRowSum;
                prefixSum[i][j] += i == 0 ? 0 : prefixSum[i - 1][j];
            }
        }
        int[][] test = prefixSum;
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = prefixSum[row2][col2];
        if (row1 > 0) {
            ans -= prefixSum[row1 - 1][col2];
        }
        if (col1 > 0) {
            ans -= prefixSum[row2][col1 - 1];
        }
        if (row1 > 0 && col1 > 0) {
            ans += prefixSum[row1 - 1][col1 - 1];
        }
        return ans;
    }
}

class Solution {
    public String breakPalindrome(String palindrome) {
        if (palindrome.length() == 1) {
            return "";
        }
        char[] ans = palindrome.toCharArray();
        int halfLength = palindrome.length() / 2;
        int ptr = 0;
        while (ptr < halfLength && palindrome.charAt(ptr) == 'a') {
            ptr += 1;
        }
        if (ptr == halfLength) {
            ans[ans.length - 1] = 'b';
        } else {
            ans[ptr] = 'a';
        }
        return new String(ans);
    }
}

class ValidWordAbbr {
    private Map<String, String> abb;

    public ValidWordAbbr(String[] dictionary) {
        abb = new HashMap<>();
        for (String word : dictionary) {
            String currAbbrev = getAbbrev(word);
            if (abb.containsKey(currAbbrev) && !abb.get(currAbbrev).equals(word)) {
                abb.put(currAbbrev, "");
            } else {
                abb.put(currAbbrev, word);
            }
        }
    }

    public boolean isUnique(String word) {
        String currAbbrev = getAbbrev(word);
        return !abb.containsKey(currAbbrev) || abb.get(currAbbrev).equals(word);
    }

    private String getAbbrev(String word) {
        if (word.length() < 3) {
            return word;
        }
        StringBuilder abbrev = new StringBuilder();
        abbrev.append(word.charAt(0)).append(word.length() - 2).append(word.charAt(word.length() - 1));
        return abbrev.toString();
    }
}

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    private Integer top;
    private Iterator<Integer> iterator;

    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        if (this.iterator.hasNext()) {
            top = this.iterator.next();
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return top;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer ans = top;
        if (this.iterator.hasNext()) {
            top = this.iterator.next();
        } else {
            top = null;
        }
        return ans;
    }

    @Override
    public boolean hasNext() {
        return top != null;
    }
}