/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if (knows(candidate, i)) {
                candidate = i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i == candidate)
                continue;
            if (!knows(i, candidate) || knows(candidate, i)) {
                return -1;
            }
        }
        return candidate;
    }
}

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs.size() == 0)
            return Character.toString((char) 258);
        String delimiter = Character.toString((char) 257);
        StringBuilder ans = new StringBuilder();
        for (String str : strs) {
            ans.append(str);
            ans.append(delimiter);
        }
        ans.deleteCharAt(ans.length() - 1);
        return ans.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        if (s.equals(Character.toString((char) 258)))
            return new ArrayList<>();
        List<String> ans = new ArrayList<>();
        String delimiter = Character.toString((char) 257);
        ans = Arrays.asList(s.split(delimiter, -1));
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        int[] ans = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (!queue.isEmpty() && queue.peek() < i - k + 1) {
                queue.poll();
            }
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            queue.offer(i);
            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[queue.peek()];
            }
        }
        return ans;
    }
}

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

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null)
            return head;
        Map<Node, Node> oldNewMap = new HashMap<>();
        Node dummy = new Node(0);
        Node newPtr = dummy;
        Node oldPtr = head;
        while (oldPtr != null) {
            Node newNode = new Node(oldPtr.val);
            oldNewMap.put(oldPtr, newNode);
            newPtr.next = newNode;
            newPtr = newPtr.next;
            oldPtr = oldPtr.next;
        }

        newPtr = dummy.next;
        oldPtr = head;
        while (newPtr != null) {
            newPtr.random = oldNewMap.get(oldPtr.random);
            newPtr = newPtr.next;
            oldPtr = oldPtr.next;
        }
        return dummy.next;
    }
}

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

    public void solve(char[][] board) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board[0].length; i++) {
            if (!visited[0][i] && board[0][i] == 'O') {
                dfs(board, 0, i, false, visited);
            }
            if (!visited[board.length - 1][i] && board[board.length - 1][i] == 'O') {
                dfs(board, board.length - 1, i, false, visited);
            }
        }
        for (int i = 0; i < board.length; i++) {
            if (!visited[i][0] && board[i][0] == 'O') {
                dfs(board, i, 0, false, visited);
            }
            if (!visited[i][board[0].length - 1] && board[i][board[0].length - 1] == 'O') {
                dfs(board, i, board[0].length - 1, false, visited);
            }
        }
        for (int row = 1; row < board.length - 1; row++) {
            for (int col = 1; col < board[0].length - 1; col++) {
                if (!visited[row][col] && board[row][col] == 'O') {
                    // dfs(board, row, col, true, visited);
                    board[row][col] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int row, int col, boolean markX, boolean[][] visited) {
        char markChar = markX ? 'X' : 'O';
        board[row][col] = markChar;
        visited[row][col] = true;
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutOfBound(board, newRow, newCol) && !visited[newRow][newCol] && board[newRow][newCol] == 'O') {
                dfs(board, newRow, newCol, markX, visited);
            }
        }
    }

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

class Solution {
    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            Node lastNode = q.peek();
            for (int i = 0; i < size; i++) {
                Node currNode = q.poll();
                currNode.next = q.peek();
                if (currNode.left != null) {
                    q.offer(currNode.left);
                }
                if (currNode.right != null) {
                    q.offer(currNode.right);
                }
                lastNode = currNode;
            }
            lastNode.next = null;
        }
        return root;
    }
}

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMinDepth = minDepth(root.left);
        int rightMinDepth = minDepth(root.right);
        return (leftMinDepth == 0 || rightMinDepth == 0) ? leftMinDepth + rightMinDepth + 1
                : Math.min(leftMinDepth, rightMinDepth) + 1;
    }
}

class Solution {
    public int numDecodings(String s) {
        Integer[] memo = new Integer[s.length()];
        return helper(s, 0, memo);
    }

    private int helper(String s, int pos, Integer[] memo) {
        if (pos == s.length()) {
            return 1;
        }
        if (memo[pos] != null) {
            return memo[pos];
        }
        if (s.charAt(pos) == '0') {
            return 0;
        }
        int singleDigitWays = helper(s, pos + 1, memo);
        int doubleDigitWays = 0;
        if (pos < s.length() - 1) {
            int currDigit = 10 * (s.charAt(pos) - '0') + (s.charAt(pos + 1) - '0');
            if (currDigit <= 26) {
                doubleDigitWays = helper(s, pos + 2, memo);
            }
        }
        memo[pos] = singleDigitWays + doubleDigitWays;
        return memo[pos];
    }
}

class Solution {
    public double myPow(double x, int n) {
        // Avoid overflow
        long N = n;

        // Test if n is negative or not
        if (n < 0) {
            x = 1 / x;
            N = -N;
        }

        // The power of ans
        long pow = 0;
        // The value of ans
        double ans = 1;

        while (pow < N) {
            // current multipler
            double currX = x;
            // The power of the current multipler
            long currPow = 1;
            // If current ans, multiplied by currX has a power less or equal to N
            // then, continue
            while (currPow + pow <= N) {
                ans *= currX;
                pow += currPow;
                currX *= currX;
                currPow <<= 1;
            }
        }
        return ans;
    }
}