public static List<Integer> findPartitionCost(List<Integer> arr, int k) {
        List<Integer> costOfPartitions = new ArrayList<>();
        
        // Calculate the cost of each partition (arr[i-1] + arr[i])
        for (int i = 1; i < arr.size(); i++) {
            costOfPartitions.add(arr.get(i - 1) + arr.get(i));
        }
        
        // Sort the partition costs
        Collections.sort(costOfPartitions);
        
        int ends = arr.get(0) + arr.get(arr.size() - 1);
        
        // Calculate min cost: smallest k-1 partitions + ends
        int minCost = ends;
        for (int i = 0; i < k - 1; i++) {
            minCost += costOfPartitions.get(i);
        }
        
        // Calculate max cost: largest k-1 partitions + ends
        int maxCost = ends;
        for (int i = costOfPartitions.size() - (k - 1); i < costOfPartitions.size(); i++) {
            maxCost += costOfPartitions.get(i);
        }
        
        return Arrays.asList(minCost, maxCost);
    }

public static List<Integer> countSkillsWithoutRequests(int numSkills, int[][] requestLogs, int timeWindow, int[] queryTimes) {
        // Sort logs by time
        Arrays.sort(requestLogs, Comparator.comparingInt(a -> a[1]));

        // Pair queries with original indices and sort by time
        int n = queryTimes.length;
        int[][] queryWithIndex = new int[n][2];
        for (int i = 0; i < n; i++) {
            queryWithIndex[i][0] = queryTimes[i];
            queryWithIndex[i][1] = i;
        }
        Arrays.sort(queryWithIndex, Comparator.comparingInt(a -> a[0]));

        int left = 0, right = 0;
        int m = requestLogs.length;
        List<Integer> result = new ArrayList<>(Collections.nCopies(n, 0));
        Map<Integer, Integer> skillCount = new HashMap<>();

        for (int[] query : queryWithIndex) {
            int queryTime = query[0];
            int idx = query[1];
            int startWindow = queryTime - timeWindow + 1;

            // Slide the right pointer forward (include logs in the window)
            while (right < m && requestLogs[right][1] <= queryTime) {
                int skill = requestLogs[right][0];
                skillCount.put(skill, skillCount.getOrDefault(skill, 0) + 1);
                right++;
            }

            // Slide the left pointer forward (remove old logs)
            while (left < m && requestLogs[left][1] < startWindow) {
                int skill = requestLogs[left][0];
                skillCount.put(skill, skillCount.get(skill) - 1);
                if (skillCount.get(skill) == 0) {
                    skillCount.remove(skill);
                }
                left++;
            }

            // Number of skills with no requests is numSkills - size of keys in skillCount
            result.set(idx, numSkills - skillCount.size());
        }

        return result;
    }