{
    'David': 20,
    'Bob': 25,
    'Eve': 28,
    'Alice': 30,
    'Charlie': 35
}

def intToRoman(num: int) -> str:
    val_sym = [
        (1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
        (100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
        (10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
    ]
    res = []
    for value, symbol in val_sym:
        while num >= value:
            res.append(symbol)
            num -= value
        if num == 0:
            break
    return ''.join(res)

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    dict_t = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1

    required = len(dict_t)
    formed = 0
    window_counts = {}

    left, right = 0, 0
    ans = float('inf'), None, None

    while right < len(s):
        character = s[right]
        window_counts[character] = window_counts.get(character, 0) + 1

        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1

        while left <= right and formed == required:
            character = s[left]

            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)

            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1

            left += 1

        right += 1

    return "" if ans[0] == float('inf') else s[ans[1]: ans[2] + 1]

def minimumAverageDifference(nums):
    n = len(nums)
    total_sum = sum(nums)  # Calculate the total sum of the array
    left_sum = 0           # Initialize left sum
    min_diff = float('inf')  # Initialize minimum difference to infinity
    min_index = -1         # Initialize minimum index

    for i in range(n):
        left_sum += nums[i]  # Update left sum with the current element
        
        # Calculate left average
        left_avg = left_sum // (i + 1)
        
        # Calculate right average
        if i < n - 1:
            right_avg = (total_sum - left_sum) // (n - i - 1)
        else:
            right_avg = 0  # If it's the last element, right average is 0
        
        # Calculate absolute difference
        diff = abs(left_avg - right_avg)

        # Update minimum difference and index if a new minimum is found
        if diff < min_diff:
            min_diff = diff
            min_index = i

    return min_index

# Example usage:
print(minimumAverageDifference([2, 5, 3, 9, 5, 3]))  # Output: 3
print(minimumAverageDifference([0]))                  # Output: 0

from collections import defaultdict

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1  # Initialize with prefix sum 0 having remainder 0
        current_sum = 0
        result = 0
        
        for num in nums:
            current_sum += num
            mod = current_sum % k
            result += prefix_counts[mod]
            prefix_counts[mod] += 1
        
        return result

def minSubArrayLen(target, nums):
    n = len(nums)
    left = 0
    curr_sum = 0
    min_len = float('inf')
    
    for right in range(n):
        curr_sum += nums[right]
        while curr_sum >= target:
            min_len = min(min_len, right - left + 1)
            curr_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

# Testing the sliding window approach:
print(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))  # Expected Output: 2
print(minSubArrayLen(4, [1, 4, 4]))           # Expected Output: 1
print(minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]))  # Expected Output: 0

def minSubArrayLenBinarySearch(target, nums):
    n = len(nums)
    # Build prefix sum array
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    min_len = float('inf')
    # Iterate over prefix sum array
    for i in range(n):
        bound = prefix[i] + target
        # Find the minimal j such that prefix[j] >= bound
        j = bisect.bisect_left(prefix, bound)
        if j <= n:
            min_len = min(min_len, j - i)
    
    return min_len if min_len != float('inf') else 0

# Testing the O(n log n) approach:
print(minSubArrayLenBinarySearch(7, [2, 3, 1, 2, 4, 3]))  # Expected Output: 2
print(minSubArrayLenBinarySearch(4, [1, 4, 4]))           # Expected Output: 1
print(minSubArrayLenBinarySearch(11, [1, 1, 1, 1, 1, 1, 1, 1]))  # Expected Output: 0

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        left = 0
        p = [0 for i in range(len(arr)+1)]
        p[1] = arr[0]
        for i in range(1,len(arr)):
            p[i+1] = p[i] +arr[i]
        total = 0
        for i in range(1,len(p)):
            l = 0
            while l<i:
                if (i-l)%2:
                    total +=  p[i]-p[l]
                l+=1
        return total

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        total = 0
        n = len(arr)
        for i, val in enumerate(arr):
            left = i + 1          # ways to choose start position
            right = n - i         # ways to choose end position
            # Count of odd-length subarrays that include arr[i]
            odd_count = ((left + 1) // 2) * ((right + 1) // 2) + (left // 2) * (right // 2)
            total += val * odd_count
        return total

solution = Solution()
print(solution.sumOddLengthSubarrays([1, 4, 2, 5, 3]))  # Output: 58
print(solution.sumOddLengthSubarrays([1, 2]))            # Output: 3

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def atMostK(k):
            count = 0
            left = 0
            for right in range(len(nums)):
                if nums[right] % 2 == 1:
                    k -= 1
                while k < 0:
                    if nums[left] % 2 == 1:
                        k += 1
                    left += 1
                count += right - left + 1
            return count
        
        return atMostK(k) - atMostK(k - 1)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        total = 0
        count_odd = 0
        l = 0
        myset = []
        
        for i in range(len(nums)):
            if nums[i] % 2:  # Check if the number is odd
                myset.append(i)  # Store the index of the odd number
                count_odd += 1
            
            if count_odd > k:
                # If we have more than k odd numbers, we need to move the left pointer
                if l:
                    l1 = (myset[l] - (myset[l - 1]))  # Distance between two odd indices
                    r = i - myset[-2]  # Distance from the second last odd index to current
                    total += l1 * r  # Count subarrays formed
                else:
                    r = i - myset[-2]
                    total += (myset[l] + 1) * r  # Count subarrays formed when l is 0
                
                l += 1  # Move the left pointer
                count_odd -= 1  # Decrease the count of odd numbers
            
        # Check for the last segment if count_odd >= k
        if count_odd >= k:
            if l:
                l1 = (myset[l] - (myset[l - 1]))
                r = (len(nums) - myset[-1])
                total += l1 * r
            else:
                r = (len(nums) - myset[-1])
                total += (myset[l] + 1) * r
        
        return total

nums = [1, 1, 2, 1, 1]
k = 3
solution = Solution()
print(solution.numberOfSubarrays(nums, k))  # Output: Number of nice subarrays