from typing import List
from itertools import groupby
import bisect

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        ans = []
        n = len(nums)
        nums = sorted(nums)

        cum_sum = [0]
        so_far = 0
        for num in nums:
            so_far += num
            cum_sum.append(so_far)

        for q in queries:
            """
            nums =       [1, 3, 6,  8]
            cum_sum = [0, 1, 4, 10, 18]
            query = 5
            left_idx = 2

            left_total : 5 * 2 - cum_sum[2] = 10 - 4 = 6
            right_total : cum_sum[-1] - cum_sum[left_idx] - 5 * (n - left_idx) = 18 - 4 - 5 * (4-2) = 14 - 10 = 4
            total : 6 + 4 = 10
            """

            # left total : q * left_idx - cum_sum[left_idx]
            # right todal : cum_sum[n+1] - cum_sum[left_idx+1] - q * (n - left_idx)

            # find the mid point
            # left_idx = bisect.bisect_left(nums, q)
            l, r = 0, n-1
            while l <= r:
                mid = (l+r) // 2
                mid_num = nums[mid]
                if mid_num <= q:
                    l = mid + 1
                else:
                    r = mid - 1
            left_idx = l
            left_total = q * left_idx - cum_sum[left_idx]
            right_total = cum_sum[-1] - cum_sum[left_idx] - q * (n - left_idx)
            tot_diff = left_total + right_total
            ans.append(tot_diff)


        return ans


print(Solution().minOperations(nums = [3,1,6,8], queries = [1,5])) # [14,10]
print(Solution().minOperations(nums = [2,9,6,3], queries = [10])) # [20]

from functools import lru_cache
from collections import Counter, defaultdict
from typing import List
from operator import mul, sub
import numpy as np

class Solution:
    def shoppingOffers(self, price: List[int], specials: List[List[int]], needs: List[int]) -> int:
        @lru_cache(None)
        def dfs(needs):
            cost = sum(map(mul, needs, price))          # cost with no specials applied
            for special in specials:
                # specPrice = special.pop()
                offer, special_price = special[:-1], special[-1]
                tmp = tuple(map(sub, needs, offer))   # reset need if special applied

                if tmp and min(tmp) < 0: continue               # special cannot be applied

                cost = min(cost, min(cost, dfs(tmp)) + special_price)  # id special best buy?
            return cost                                 # return best cost for needs
        return dfs(tuple(needs))

print(Solution().shoppingOffers(price = [2,5], specials = [[3,0,5],[1,2,10]], needs = [3,2]))
print(Solution().shoppingOffers(price = [2,3,4], specials = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]))
print(Solution().shoppingOffers(price = [3,4], specials = [[1,2,3],[1,2,5]], needs = [2,2]))

from collections import deque
from math import ceil
from typing import List

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        return (pow(5, (n + 1) // 2, MOD) * pow(4, n // 2, MOD)) % MOD


print(Solution().countGoodNumbers(110000000000))

from typing import List
import numpy as np
class Solution:
    def numberOfCleanRooms(self, room: List[List[int]]) -> int:

        H, W = len(room), len(room[0])

        visited = [[0 for _ in range(W)] for _ in range(H)]

        dys = [0, 1, 0, -1]
        dxs = [1, 0, -1, 0]
        ans = 0

        def recur(y, x, d):
            if visited[y][x] > 4:
                return

            if visited[y][x] == 0:
                nonlocal ans
                ans += 1
            visited[y][x] += 1

            ny, nx = y + dys[d], x + dxs[d]

            # in room
            if (0 <= ny < H and 0 <= nx < W) and room[ny][nx] == 0:
                recur(ny, nx, d)
                return

            for i in range(1, 5):
                next_d = (d + i) % 4
                ny, nx = y  + dys[next_d], x + dxs[next_d]
                if (0 <= ny < H and 0 <= nx < W) and room[ny][nx] == 0:
                    recur(ny, nx, next_d)
                    return

        recur(0, 0, 0)
        return ans



# print(Solution().numberOfCleanRooms(room = [[0,0,0],[1,1,0],[0,0,0]])) # 7
# print(Solution().numberOfCleanRooms(room = [[0,1,0],[1,0,0],[0,0,0]])) # 1
# print(Solution().numberOfCleanRooms(room = [[0,0,0],[0,0,0],[0,0,0]])) # 8

# room = [[0,0,0,1],[0,1,0,1],[1,0,0,0]]
# print(np.array(room))
# print(Solution().numberOfCleanRooms(room)) # 7

from typing import List
from collections import Counter
import math

class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        def is_valid(a, b):
             return int(math.sqrt(a+b)) ** 2 == a + b

        ans = 0
        c = Counter(nums)
        lnum = len(nums)
        nums = list(c.keys())

        def recur(l):
            # print(l)
            if len(l) == lnum:
                nonlocal ans
                ans += 1
                return

            for num in nums:
                if c[num] == 0: continue

                c[num] -= 1 # update state (for backtracking)
                if not l:
                    recur(l + [num])
                else:
                    if is_valid(l[-1], num):
                        # if this recursion ends up
                        # successfully, we only visit this path once
                        recur(l + [num])
                c[num] += 1 # backtrack (return to previous state)
        recur([])

        return ans

# print(Solution().numSquarefulPerms([1,17,8]))
# print(Solution().numSquarefulPerms([1,1]))
print(Solution().numSquarefulPerms([2,2,2,2,2,2,2,2,2,2,2,2]))

from math import gcd
def nlcm(num): # least common multiple
    answer = num[0]
    for n in num:
        answer = n * answer // int(gcd(n, answer))

    return answer

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(nlcm([2,6,8,14]));
# {2:3, 3:1, 7:1} => 8 * 3 * 7 = 168

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:

        ans = 0

        def recur(node):

            if not node:
                return (0, 0)

            left_tot, left_cnt = recur(node.left)
            right_tot, right_cnt = recur(node.right)

            cnt = left_cnt + right_cnt + 1
            tot = left_tot + right_tot + node.val

            nonlocal ans
            if tot // cnt == node.val:
                ans += 1

            return (tot, cnt)

        recur(root)
        return ans

def test():
    mat = [[0] * 5 for _ in range(5)]
    seen = [[False] * 5 for _ in range(5)]
    start = (2, 2)
    st1 = list()
    st2 = list()
    st1.append(start)
    dy = [0, 0, 1, -1]
    dx = [-1, 1, 0, 0]
    depth = 1

    print()
    while (st1 or st2):
        print(f'depth: {depth}, stack1: {st1}, stack2: {st2}')
        stlen = len(st1) if depth % 2 == 1 else len(st2)
        while (stlen):
            stlen -= 1

            (y,x) = st1.pop() if depth % 2 == 1 else st2.pop()
            seen[y][x] = True
            mat[y][x] = depth

            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]

                if ny < 0 or ny > 4 or nx < 0 or nx > 4: continue
                if seen[ny][nx]: continue

                seen[ny][nx] = True

                if depth % 2 == 1: st2.append((ny,nx))
                else: st1.append((ny,nx))
        depth += 1
    print()
    for i in mat:
        print(i)
    print()
test()

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def max_gain(node):
            nonlocal max_sum
            if not node:
                return 0

            # max sum on the left and right sub-trees of node
            left_gain = max(max_gain(node.left), 0) # this handles negative sum
            right_gain = max(max_gain(node.right), 0) # this handles negative sum

            # the price to start a new path where `node` is a highest node
            price_newpath = node.val + left_gain + right_gain

            # update max_sum if it's better to start a new path
            max_sum = max(max_sum, price_newpath)

            # for recursion :
            # return the max gain if continue the same path
            return node.val + max(left_gain, right_gain)

        max_sum = float('-inf')
        max_gain(root)
        return max_sum

# Input: root = [1,2,3]
# Output: 6
# Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
def test1():

    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)

    n1.left = n2
    n1.right = n3

    assert 6 == Solution().maxPathSum(n1)

# Example 2:
# Input: root = [-10,9,20,null,null,15,7]
# Output: 42
# Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
def test2():
    n1 = TreeNode(-10)
    n2 = TreeNode(9)
    n3 = TreeNode(20)
    n4 = TreeNode(15)
    n5 = TreeNode(7)

    n1.left = n2
    n1.right = n3
    n3.left = n4
    n3.right = n5

    assert 42 == Solution().maxPathSum(n1)


test1()
test2()

from collections import deque
from typing import List


class Solution:
    def minSwaps(self, data: List[int]) -> int:
        num_data = len(data)
        window_size = sum(data)

        if window_size == 0:
            return 0

        # precalculate number of zeros [0, i) (from idx 0 to idx i)
        # idx2zeros[1] : data[:1] 사이의 0의 개수
        # idx2zeros[num_data] : data[:num_data] 사이의 0의 개수
        idx2zeros = [0]
        zcnt = 0
        for num in data:
            if num == 0:
                zcnt += 1
            idx2zeros.append(zcnt)

        # have default value
        min_zeros_so_far = idx2zeros[window_size] - idx2zeros[0]
        for i in range(num_data - window_size + 1):

            # range : [i, i + window_size)
            cur_range_zeros = idx2zeros[i+window_size] - idx2zeros[i]

            # update min_zeros_so_far if we find better solution
            min_zeros_so_far = min(min_zeros_so_far, cur_range_zeros)
        return min_zeros_so_far


print(Solution().minSwaps([1, 0, 1, 0, 1]))
print(Solution().minSwaps([0, 0, 0, 1, 0]))
print(Solution().minSwaps([1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1]))

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # N E S W
        dys = [1, 0, -1, 0]
        dxs = [0, 1, 0, -1]

        def change_dir(direction, c):
            if c == "L":
                direction = (direction - 1) % 4
            else:
                direction = (direction + 1) % 4
            return direction
        y, x = 0, 0
        direction = 0
        dy, dx = dys[direction], dxs[direction]
        for inst in instructions * 4:
            if inst == 'G':
                y += dy
                x += dx
            else:
                direction = change_dir(direction, inst)
                dy, dx = dys[direction], dxs[direction]
        return True if y == 0 and x == 0  else False

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:

        ans = None

        while root:
            if p.val >= root.val: # if p.val is higher or equal to root.val -> go right
                root = root.right
            else: # if p.val is smaller than root.val -> go left and current node as successor
                ans = root
                root = root.left

        return ans

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break

        # Find the "entrance" to the cycle.
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]

        return hare

from collections import defaultdict
class RangeFreqQuery:

    def __init__(self, arr: List[int]):

        self.num2indices = defaultdict(list)
        for idx, num in enumerate(arr):
            self.num2indices[num].append(idx)

    def query(self, left: int, right: int, value: int) -> int:

        # find how many indices are in range [left, right]
        indices = self.num2indices[value]
        if not indices:
            return 0

        llen = len(indices)
        # find lower bound
        # find indices that satisfy the condition but among them, lowest index
        lo, up = 0, llen
        while lo < up:
            mid = (lo+up) // 2
            mid_val = indices[mid]

            if left <= mid_val:
                up = mid
            else:
                lo = mid + 1
        lower_bound = lo

        # find uppper bound
        lo, up = 0, llen
        while lo < up:
            mid = (lo + up) // 2
            mid_val = indices[mid]

            if right < mid_val:
                up = mid
            else:
                lo = mid + 1
        upper_bound = lo
        return upper_bound - lower_bound

# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)

from collections import Counter
from typing import List
from heapq import *

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:

        heap = []

        for i in range(min(k, len(nums1))):
            for j in range(min(k, len(nums2))):
                n1, n2 = nums1[i], nums2[j]
                tot = n1 + n2

                if len(heap) < k:
                    heappush(heap, (-tot, n1, n2))
                else: # already heap size condition is satisfied
                    if tot > -heap[0][0]: # if tot (newly added) is greater than the largest element in the heap
                        break
                    else: # updating heap with the new element (because we found a smaller tot)
                        heappop(heap)
                        heappush(heap, (-tot, n1, n2))

        return [[n1, n2] for _, n1, n2 in heap]


# print(Solution().kSmallestPairs(nums1 = [1,1,2], nums2 = [1,2,3], k = 10))
print(Solution().kSmallestPairs(nums1 = [1,1,2], nums2 = [1,2,3], k = 2))
# print(Solution().kSmallestPairs(nums1 = [1,7,11], nums2 = [2,4,6], k = 3))
# print(Solution().kSmallestPairs(nums1 = [1,2], nums2 = [3], k = 3))

from collections import Counter
from typing import List
from heapq import *

inf = float('inf')

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        gi = 0
        def helper(min_limit, max_limit):
            nonlocal gi
            if gi == len(preorder):
                return True

            root = preorder[gi]
            print(f'{root, min_limit, max_limit = }')
            if not min_limit < root < max_limit:
                return False

            gi += 1
            left = helper(min_limit, root)
            right = helper(root, max_limit)

            return left or right

        return helper(-inf, inf)

class Solution2:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        min_limit = -inf
        stack = []

        for num in preorder:
            print(f'{stack, num = }')
            while stack and stack[-1] < num:
                min_limit = stack.pop()

            print(f'{stack, min_limit = }')
            if num <= min_limit:
                return False

            stack.append(num)

        return True

print(Solution().verifyPreorder([5,2,1,3,6])) # True
print(Solution().verifyPreorder([5,2,6,1,3])) # True