class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        // search left 
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int pivot = left + (right - left) / 2;
            if(nums[pivot] >= target){
                // we shrink to left 
                right = pivot - 1;
            }else{
                // it is too small
                left = pivot + 1;
            }
        }
        int p1 = left;
        left = 0; right = nums.length - 1;
        // find right boundry
        while(left <= right){
            int pivot = left + (right - left) / 2;
            if(nums[pivot] > target){
                // we shrink to left 
                right = pivot - 1;
            }else{
                // it is too small
                left = pivot + 1;
            }
        }
        int p2 = right;
        return p2 - p1 + 1 > nums.length /2;
    }
}

class Solution {
    public int minFlips(int a, int b, int c) {
        int res = 0;
        while(a != 0 || b != 0 || c!= 0){
            // there is more we going to exampe
            if((c & 1) == 1){
                // we have c curr bit at one 
                if ((a & 1) == 0 && (b & 1) == 0) {
                    // we need to flip this c
                    res++;
                }
            }else{
                res += (a & 1) + (b & 1); // flip a or b to 0 if needed
            }
            //exam next bit

            a >>= 1;
            b >>= 1;
            c >>= 1;

        }
        return res;
    }
}

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // build the graph 
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i ++){
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i < n; i ++){
            if (manager[i] != -1) {
                graph.get(manager[i]).add(i);
            }
        }

        // do the bfs
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{headID,informTime[headID]});
        int res = 0;
        while(!q.isEmpty()){
            int[] curr = q.poll();
            res = Math.max(res,curr[1]);
            for(int next : graph.get(curr[0])){
                q.add(new int[]{next,curr[1] + informTime[next]});
            }
        }
        return res;
    }
}

class Solution {
    public int maximumDetonation(int[][] bombs) {
        // we can treat as a graph
        Map<Integer,List<Integer>> graph = new HashMap<>();
        int n = bombs.length;

        // building the graph
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
                // we need to make sure we have different bomb 
                if(i != j){
                    int xi = bombs[i][0], yi = bombs[i][1], ri = bombs[i][2];
                    int xj = bombs[j][0], yj = bombs[j][1];

                    // if xi can trigger xj we create that edge
                    if((long) ri * ri >= (long)(xi - xj) * (xi - xj) + (long)(yi - yj) * (yi - yj)){
                        graph.putIfAbsent(i,new ArrayList<>());
                        graph.get(i).add(j);
                    }
                }
            }
        }

        // now we can do dfs or bfs 
        int res = 0;
        for(int i = 0; i < n; i ++){
            int count = bfs(i, new HashSet<>(),graph);
            res = Math.max(res,count);
        }
        return res;
    }
    private int bfs(int start, Set<Integer> visited, Map<Integer,List<Integer>> graph){
        Queue<Integer> q = new LinkedList<>();
        visited.add(start);
        q.add(start);
        int res = 0;
        while(!q.isEmpty()){
            res ++;
            int curr = q.poll();
            if(graph.containsKey(curr)){
                for(int next : graph.get(curr)){
                    if(!visited.contains(next)){
                        // this is a new valid bomb
                        q.add(next);
                        visited.add(next);
                    }
                }
            }

            
        }
        return res;
    }
}

class UndergroundSystem {
    HashMap<Integer,Pair<String,Integer>> checkIn;
    HashMap<String,Pair<Double,Integer>> log;
    public UndergroundSystem() {
        checkIn = new HashMap<>();
        log = new HashMap<>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        // check in the customer 
        checkIn.putIfAbsent(id,new Pair<>(stationName,t));
    }
    
    public void checkOut(int id, String stationName, int t) {
        Pair<String,Integer> info = checkIn.get(id);
        String startStation = info.getKey();
        int startTime = info.getValue();
        String route = startStation + "->" + stationName;
        double tripTime = t - startTime;

        if(log.containsKey(route)){
            double loggedTime = log.get(route).getKey();
            int loggedTrip = log.get(route).getValue();
            log.put(route,new Pair<>(tripTime + loggedTime, loggedTrip + 1));
        }else{
            log.put(route,new Pair<>(tripTime,1));
        }
        // remove the entry
        checkIn.remove(id);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        // Lookup how many times this journey has been made, and the total time.
        String routeKey = startStation + "->" + endStation;
        Double totalTime = log.get(routeKey).getKey();
        int totalTrips = log.get(routeKey).getValue();
        // The average is simply the total divided by the number of trips.
        return totalTime / totalTrips;
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.checkIn(id,stationName,t);
 * obj.checkOut(id,stationName,t);
 * double param_3 = obj.getAverageTime(startStation,endStation);
 */

class ParkingSystem {
    int[] lot;
    public ParkingSystem(int big, int medium, int small) {
        lot = new int[]{big,medium,small};
    }
    
    public boolean addCar(int carType) {
        if(lot[carType - 1] == 0) return false;
        lot[carType - 1] --;
        return true;
    }
}

class TicTacToe {
    int[] rows,cols;
    int diagonal,antiDiagonal;

    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        diagonal = 0;
        antiDiagonal = 0;    
    }
    
    public int move(int row, int col, int player) {
        int n = rows.length;
        // determine the mark by player 
        int mark = (player == 1) ? 1 : -1;
        // mark the row and col 
        rows[row] += mark;
        cols[col] += mark;
        // mark the diagonal or antiDiagonal if applies
        if(row == col) diagonal += mark;
        if(col == (n - row - 1)) antiDiagonal += mark;
        // if any row or col scores n that means our new mark connected a row col diagonal or antiDiagonal;
        if(Math.abs(rows[row]) == n|| Math.abs(cols[col]) == n || Math.abs(diagonal) == n || Math.abs(antiDiagonal)  == n) return player;
        // no winer
        return 0;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

class Solution {
    Integer[][] memo;
    int newCuts[];
    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        memo = new Integer[m + 2][m + 2];
        newCuts = new int[m + 2];
        System.arraycopy(cuts, 0, newCuts, 1, m);
        newCuts[m + 1] = n;
        Arrays.sort(newCuts);
        return dp(0,newCuts.length - 1);
    }
    private int dp(int left, int right){
        // base case 
        if(right - left == 1) return 0;

        if(memo[left][right] != null) return memo[left][right];

        int res = Integer.MAX_VALUE;
        for(int pivot = left + 1; pivot < right; pivot ++){
            int cost = dp(left,pivot) + dp(pivot,right) + newCuts[right] - newCuts[left];
            res = Math.min(res,cost);
        }
        memo[left][right] = res;
        return res;
    }
}

class Solution {
    Integer[] dp;
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        dp = new Integer[n + 1];
        int res = helper(stoneValue,0);
        if(res > 0){
            return "Alice";
        }
        if(res < 0){
            return "Bob";
        }
        return "Tie";
    }
    private int helper(int[] stones, int curr){
        // base case 
        if(curr == stones.length) return 0; // no more stone 
        if(dp[curr] != null) return dp[curr]; // solved case

        // our socre is what we have - what opponent can have
        int res = stones[curr] - helper(stones,curr + 1); 
        if(curr + 2 <= stones.length){
            // we can take up to 2 stones
            res = Math.max(res,stones[curr] + stones[curr + 1] - helper(stones,curr + 2));
        }
        if(curr + 3 <= stones.length){
            res = Math.max(res,stones[curr] + stones[curr + 1] + stones[curr + 2] - helper(stones,curr + 3));
        }
        return dp[curr] = res;
    }
}

class Solution {
    Integer[][][] memo;
    public int stoneGameII(int[] piles) {
        memo = new Integer[2][piles.length + 1][piles.length + 1];
        return stoneGame(piles,0,1,0);
    }
    private int stoneGame(int[] piles, int curr, int M, int alex){
        // base case 
        if(curr >= piles.length) return 0; // no more stone 
        if(memo[alex][curr][M] != null) return memo[alex][curr][M];
        int res = alex == 1 ? 1000000 : -1;
        int stones = 0;
        for(int x = 1; x <= Math.min(2 * M, piles.length - curr); x ++){
            stones += piles[curr + x - 1];
            if(alex == 0){
                res = Math.max(res,stones + stoneGame(piles,curr + x,Math.max(M,x),1));
            }else{
                res = Math.min(res,stoneGame(piles,curr + x, Math.max(M,x),0));
            }
        }
        return memo[alex][curr][M] = res;
    }
}