class ExamRoom {
    private Map<Integer, int[]> endMap;
    private Map<Integer, int[]> startMap;
    private TreeSet<int[]> intervals;
    private int N;

    public ExamRoom(int n) {
        endMap = new HashMap<>();
        startMap = new HashMap<>();
        intervals = new TreeSet<>((a, b) -> {
            int distanceA = distance(a);
            int distanceB = distance(b);
            if (distanceA != distanceB) {
                return distanceA - distanceB;
            }
            return b[0] - a[0];
        });
        N = n;
        intervals.add(new int[] { -1, N });
    }

    public int seat() {
        Map<Integer, int[]> sM = this.startMap;
        Map<Integer, int[]> eM = this.endMap;
        TreeSet<int[]> inter = this.intervals;
        int[] longestInterval = intervals.last();
        int ans = -1;
        if (longestInterval[0] == -1) {
            ans = 0;
        } else if (longestInterval[1] == N) {
            ans = N - 1;
        } else {
            ans = (longestInterval[1] + longestInterval[0]) / 2;
        }
        removeInterval(longestInterval);
        addInterval(new int[] { longestInterval[0], ans });
        addInterval(new int[] { ans, longestInterval[1] });
        return ans;
    }

    public void leave(int p) {
        int[] leftInterval = endMap.get(p);
        int[] rightInterval = startMap.get(p);
        removeInterval(leftInterval);
        removeInterval(rightInterval);
        addInterval(new int[] { leftInterval[0], rightInterval[1] });
    }

    private void addInterval(int[] interval) {
        startMap.put(interval[0], interval);
        endMap.put(interval[1], interval);
        intervals.add(interval);
    }

    private void removeInterval(int[] interval) {
        startMap.remove(interval[0]);
        endMap.remove(interval[1]);
        intervals.remove(interval);
    }

    private int distance(int[] interval) {
        if (interval[0] == -1) {
            return interval[1];
        }
        if (interval[1] == N) {
            return N - 1 - interval[0];
        }
        return (interval[1] - interval[0]) / 2;
    }

    private void print() {
        System.out.println(startMap);
        System.out.println(endMap);
        System.out.println(intervals);
    }
}

class Solution {
    public int maxDistToClosest(int[] seats) {
        int lastSeated = -1, ans = 0;
        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 1) {
                ans = lastSeated < 0 ? i : Math.max(ans, (i - lastSeated) / 2);
                lastSeated = i;
            }
        }
        ans = Math.max(ans, (seats.length - 1 - lastSeated));
        return ans;
    }
}

class Solution {
    public int minJumps(int[] arr) {
        Map<Integer, Set<Integer>> numMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            numMap.computeIfAbsent(arr[i], a -> new HashSet<>()).add(i);
        }
        Deque<Integer> q = new ArrayDeque<>();
        boolean[] visited = new boolean[arr.length];
        q.offer(0);
        visited[0] = true;
        int steps = 0;
        while (!q.isEmpty()) {
            for (int i = q.size(); i > 0; i--) {
                int currPos = q.poll();
                if (currPos == arr.length - 1) {
                    return steps;
                }
                int left = currPos - 1;
                if (left >= 0 && !visited[left]) {
                    q.offer(left);
                    visited[left] = true;
                }
                int right = currPos + 1;
                if (right < arr.length && !visited[right]) {
                    q.offer(right);
                    visited[right] = true;
                }
                if (numMap.containsKey(arr[currPos])) {
                    Set<Integer> neighbors = numMap.get(arr[currPos]);
                    for (Integer neighbor : neighbors) {
                        if (!visited[neighbor]) {
                            q.offer(neighbor);
                            visited[neighbor] = true;
                        }
                    }
                    numMap.remove(arr[currPos]);
                }
            }
            steps += 1;
        }
        return -1;
    }
}

class Solution {
    public boolean canReach(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(start);
        visited[start] = true;
        while (!q.isEmpty()) {
            int currPos = q.poll();
            if (arr[currPos] == 0) {
                return true;
            }
            int nextPosOne = currPos + arr[currPos];
            if (nextPosOne < arr.length && !visited[nextPosOne]) {
                q.offer(nextPosOne);
                visited[nextPosOne] = true;
            }
            int nextPosTwo = currPos - arr[currPos];
            if (nextPosTwo >= 0 && !visited[nextPosTwo]) {
                q.offer(nextPosTwo);
                visited[nextPosTwo] = true;
            }
        }
        return false;
    }
}

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

    private int helper(char[] sArray, int left, int right, Integer[][] memo) {
        if (left > right) {
            return 0;
        }
        if (left == right) {
            return 1;
        }
        if (memo[left][right] != null) {
            return memo[left][right];
        }
        if (sArray[left] == sArray[right]) {
            return memo[left][right] = helper(sArray, left + 1, right - 1, memo) + 2;
        }
        return memo[left][right] = Math.max(helper(sArray, left + 1, right, memo),
                helper(sArray, left, right - 1, memo));
    }
}

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dictSet = new HashSet<>(wordDict);
        List<String> ans = new ArrayList<>();
        helper(ans, s, new StringBuilder(), dictSet, 0);
        return ans;
    }

    private void helper(List<String> ans, String s, StringBuilder curr, Set<String> dictSet, int ptr) {
        if (ptr == s.length()) {
            ans.add(curr.toString().trim());
            return;
        }
        for (int i = ptr + 1; i <= s.length(); i++) {
            String currString = s.substring(ptr, i);
            if (dictSet.contains(currString)) {
                curr.append(currString).append(' ');
                helper(ans, s, curr, dictSet, i);
                curr.delete(curr.length() - (currString.length() + 1), curr.length());
            }
        }
    }
}

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int ans = 0;
        PriorityQueue<Integer> diffQueue = new PriorityQueue<>();
        for (int i = 1; i < heights.length; i++) {
            int diff = heights[i] - heights[i - 1];
            if (diff <= 0) {
                ans += 1;
            } else {
                diffQueue.offer(diff);
                if (diffQueue.size() > ladders) {
                    int minDiff = diffQueue.poll();
                    bricks -= minDiff;
                    if (bricks >= 0) {
                        ans += 1;
                    } else {
                        break;
                    }
                } else {
                    ans += 1;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        if (tokens.length == 0 || power < tokens[0])
            return 0;
        int score = 0, ans = 0;
        int left = 0, right = tokens.length - 1;
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score += 1;
                left += 1;
            } else {
                if (right != left) {
                    power += tokens[right];
                    score -= 1;
                    right -= 1;
                } else {
                    break;
                }
            }
        }
        return score;
    }
}

class FreqStack {
    private Map<Integer, Integer> freqMap;
    private Map<Integer, Deque<Integer>> freqStack;
    private int maxFreq;

    public FreqStack() {
        freqMap = new HashMap<>();
        freqStack = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        int freq = freqMap.getOrDefault(val, 0) + 1;
        freqMap.put(val, freq);
        freqStack.computeIfAbsent(freq, a -> new ArrayDeque<>()).push(val);
        maxFreq = Math.max(maxFreq, freq);
    }

    public int pop() {
        int ans = freqStack.get(maxFreq).pop();
        freqMap.put(ans, freqMap.get(ans) - 1);
        if (freqStack.get(maxFreq).isEmpty()) {
            maxFreq -= 1;
        }
        return ans;
    }
}

class Solution {
    private Map<Integer, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        List<TreeNode> ans = new ArrayList<>();
        if (n == 1) {
            ans.add(new TreeNode(0));
        } else if (n % 2 == 1) {
            for (int i = 1; i < n; i += 2) {
                int j = n - 1 - i;
                for (TreeNode left : allPossibleFBT(i)) {
                    for (TreeNode right : allPossibleFBT(j)) {
                        TreeNode currRoot = new TreeNode(0);
                        currRoot.left = left;
                        currRoot.right = right;
                        ans.add(currRoot);
                    }
                }
            }
        }
        memo.put(n, ans);
        return ans;
    }
}