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

1
5 4
5 2 3 2 5
1 4 9 12 20
1 2
7 7
99 100
3 3

17
12
0
14

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        # Step 1: Compute prefix sum
        p = [0]  # Prefix sum array initialized with 0
        for i in range(len(nums)):
            p.append(p[-1] + nums[i])  # Store cumulative sum
        
        # Step 2: Iterate through the array and check pivot condition
        for i in range(1, len(p)):
            left_sum = p[i] - nums[i - 1]  # Sum of elements to the left of index i-1
            right_sum = p[-1] - p[i]       # Sum of elements to the right of index i-1
            
            if left_sum == right_sum:
                return i - 1  # Return the pivot index
        
        return -1  # If no pivot index is found

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # Step 1: Define movement directions (North, East, South, West)
        directions = [(0,1), (1,0), (0,-1), (-1,0)]  
        x, y, max_dist, d = 0, 0, 0, 0  # Robot starts at (0,0), facing North
        
        # Step 2: Convert obstacles list into a set for quick lookups
        obstacle_set = set(map(tuple, obstacles))  

        # Step 3: Process each command
        for command in commands:
            if command == -2:  # Turn left
                d = (d - 1) % 4
            elif command == -1:  # Turn right
                d = (d + 1) % 4
            else:  # Move forward k steps
                for _ in range(command):
                    next_x, next_y = x + directions[d][0], y + directions[d][1]
                    
                    # Stop moving if an obstacle is hit
                    if (next_x, next_y) in obstacle_set:
                        break  
                    
                    x, y = next_x, next_y  # Update position
                    max_dist = max(max_dist, x*x + y*y)  # Update max distance
        
        return max_dist  # Return max squared Euclidean distance

x + 2x + 4x + … + 2ᵏ⁻¹x = n

7
3
6
7
21
28
999999999
999999984

1
2
1
7
4
333333333
333333328

t = int(input())
while t > 0:
    t-=1
    num = int(input())
    k = 3
    n = 4
    while num % k:
        k += n
        n *= 2
    print(num // k)

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the mapping of integers to Roman numerals
        val = [
            1000, 900, 500, 400,
            100, 90, 50, 40,
            10, 9, 5, 4,
            1
        ]
        syms = [
            "M", "CM", "D", "CD",
            "C", "XC", "L", "XL",
            "X", "IX", "V", "IV",
            "I"
        ]
        
        roman_num = ''
        i = 0
        while num > 0:
            for _ in range(num // val[i]):
                roman_num += syms[i]
                num -= val[i]
            i += 1
        return roman_num

# Example usage:
sol = Solution()
print(sol.intToRoman(1994))  # Output: "MCMXCIV"

class Solution:
    def intToRoman(self, num: int) -> str:
        # Mapping of integer values to Roman numerals
        roman_map = {
            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'
        }
        
        roman_numeral = ''
        
        for value in roman_map.keys():
            while num >= value:
                roman_numeral += roman_map[value]
                num -= value
        
        return roman_numeral

# Example usage:
sol = Solution()
print(sol.intToRoman(58))  # Output: "LVIII"

class Solution:
    def intToRoman(self, num: int) -> str:
        # Define the mapping of integers to Roman numerals
        roman_map = [
            (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')
        ]
        
        def convert(n):
            if n == 0:
                return ""
            for value, symbol in roman_map:
                if n >= value:
                    return symbol + convert(n - value)
        
        return convert(num)

# Example usage:
sol = Solution()
print(sol.intToRoman(3))  # Output: "III"

class Solution:
    def intToRoman(self, num: int) -> str:
        roman = {1: "I", 5: "V", 10: "X", 50: "L", 100: "C", 500: "D", 1000: "M"}
        s = ""
        st = str(num)
        length = len(st)
        
        for ch in st:
            i = int(ch)
            # Calculate the current power of ten (e.g., 1000, 100, 10, 1)
            place = 10 ** (length - 1)
            if i == 4 or i == 9:
                # For subtractive cases, e.g., 4 -> "IV" and 9 -> "IX"
                s += roman[place] + roman[place * (i + 1)]
            else:
                if i >= 5:
                    s += roman[place * 5]
                    s += roman[place] * (i - 5)
                else:
                    s += roman[place] * i
            length -= 1
        return s

# Example usage:
if __name__ == '__main__':
    sol = Solution()
    print(sol.intToRoman(3749))  # Output: "MMMDCCXLIX"

cᵢ = aᵢ + bᵢ   (1 ≤ i ≤ n)

5
4
1 2 1 2
1 2 1 2
6
1 2 3 3 2 1
1 1 1 1 1 1
3
1 1 1
1 1 1
6
1 52 52 3 1 3
59 4 3 59 3 4
4
100 1 100 1
2 2 2 2

YES
YES
NO
YES
NO

t = int(input())
while t>0:
    t-=1
    lenght = int(input())
    arr1 = list(map(int,input().split()))
    arr2 = list(map(int,input().split()))
    hash1 = set()
    hash2 = set()
    for i in range(len(arr1)):
        hash1.add(arr1[i])
        hash2.add(arr2[i])
    if (len(hash2)<=1 and len(hash1) <=2 )or (len(hash1)<=1 and len(hash2) <=2 ):
        print("NO")
    else:
        print("YES")