from typing import Callable


class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack: list[int] = []
        operators: dict[str, Callable[[int, int], int]] = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a / b),
        }
        for token in tokens:
            if token in operators:
                b, a = stack.pop(), stack.pop()
                stack.append(operators[token](a, b))
            else:
                stack.append(int(token))
        return stack[0]

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        result = [0] * len(temperatures)
        stack = []
        for r in range(len(temperatures)):
            while stack and temperatures[stack[-1]] < temperatures[r]:  # l < r
                l = stack.pop()
                result[l] = r - l
            stack.append(r)
        return result

import heapq
from collections import Counter
from itertools import chain, islice


class Solution:  # O(n) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        buckets = [[] for _ in nums]
        for n, c in Counter(nums).items():
            buckets[-c].append(n)
        return list(islice(chain.from_iterable(buckets), k))


class Solution1:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [heapq.heappop(heap)[1] for _ in range(k)]


class Solution2:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [x[1] for x in heapq.nsmallest(k, heap)]


class Solution3:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        return [n for n, _ in Counter(nums).most_common(k)]

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        ht: dict[str, list[str]] = {}
        for s in strs:
            key = ''.join(sorted((s)))
            ht[key] = ht.get(key, [])
            ht[key].append(s)
        return list(ht.values())

from typing import Optional


# 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 Solution1:
    def largestValues(self, root: Optional[TreeNode]) -> list[int]:
        result, nodes = [], [x for x in [root] if x]
        while nodes:
            result.append(max(x.val for x in nodes))
            _next = []
            _next.extend([x.left for x in nodes if x.left])
            _next.extend([x.right for x in nodes if x.right])
            nodes = _next
        return result


class Solution:
    # https://leetcode.com/problems/find-largest-value-in-each-tree-row/solutions/99000/python-bfs/
    def largestValues(self, root: Optional[TreeNode]) -> list[int]:
        result, nodes = [], [root]
        while any(nodes):
            result.append(max(x.val for x in nodes))
            nodes = [x for n in nodes for x in [n.left, n.right] if x]
        return result

class SolutionR1:  # O(n*n) / O(n) ? str slice
    def numDecodings(self, s: str) -> int:
        m = {'': 1}

        def recur(s=s):
            if s in m:
                return m[s]
            m[s] = 0
            if s[0] != '0':
                m[s] += recur(s[1:])
            if 10 <= int(s[:2]) <= 26:
                m[s] += recur(s[2:])
            return m[s]

        return recur()


class SolutionR2:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        m = {len(s): 1}

        def recur(i=0):
            if i in m:
                return m[i]
            m[i] = 0
            if s[i] != '0':
                m[i] += recur(i + 1)
            if 10 <= int(s[i : i + 2]) <= 26:
                m[i] += recur(i + 2)
            return m[i]

        return recur()


class Solution1:  # O(n) / O(n)
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0], dp[1] = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            if s[i + 1] != '0':
                dp[i + 2] += dp[i + 1]
            if 10 <= int(s[i : i + 2]) <= 26:
                dp[i + 2] += dp[i]
        return dp[-1]


class Solution2:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            c = 0
            if s[i + 1] != '0':
                c += b
            if 10 <= int(s[i : i + 2]) <= 26:
                c += a
            a, b = b, c
        return b


class Solution3:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b = 1, int(s[0] != '0')
        for i in range(len(s) - 1):
            one, two = s[i + 1] != '0', 10 <= int(s[i : i + 2]) <= 26
            a, b = b, b * one + a * two
        return b


class Solution4:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            tmp = b
            if c == '0':
                b = 0
            if 10 <= int(p + c) <= 26:
                b += a
            a, p = tmp, c
        return b


class Solution:  # O(n) / O(1)
    def numDecodings(self, s: str) -> int:
        a, b, p = 0, int(bool(s)), ''
        for c in s:
            one, two = c != '0', 10 <= int(p + c) <= 26
            a, b, p = b, b * one + a * two, c
        return b

'''
f(k) = (n/k)^k
-> ln(f(k)) = k ln(n/k)
-> d ln(f(k)) / d k = ln(n/k) + k(-1/k)
-> d f(k) / f(k) d k = ln(n/k) - 1
-> f′(k) = f(k) (ln(n/k) - 1)
find the maximum:
f′(k) = 0
-> ln(n/k) = 1
-> n/k = e, 2 or 3
'''


import math


class Solution1:  # O(n)
    # https://leetcode.com/problems/integer-break/solutions/4136961/easy-olog-n-time-with-o1-space-complexity-easy-math-solution-with-proofs/
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        result = 1
        while n > 4:
            result *= 3
            n -= 3
        return n * result


class Solution2:  # O(log(n))
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return 2 ** (-n % 3) * 3 ** ((n - 4) // 3 + (n - 1) % 3)


class Solution:  # O(1)
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return int(math.pow(2, -n % 3) * math.pow(3, (n - 4) // 3 + (n - 1) % 3))

class Solution:
    def rob(self, nums: list[int]) -> int:
        def _rob(start: int, stop: int):
            a, b = 0, 0
            for i in range(start, stop):
                a, b = b, max(a + nums[i], b)
            return b

        return max(_rob(0, len(nums) - 1), _rob(1, len(nums)))

class Solution:
    def rob(self, nums: list[int]) -> int:
        a, b = 0, 0
        for n in nums:
            a, b = b, max(a + n, b)
        return b

class Solution1:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result, chars = 0, set()
        for j, c in enumerate(s):
            while c in chars:
                i = j - len(chars)
                chars.remove(s[i])
            chars.add(c)
            result = max(result, len(chars))
        return result


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result, i, chars = 0, 0, {}
        for j, char in enumerate(s):
            i = max(i, chars.get(char, -1) + 1)
            chars[char] = j
            result = max(result, j - i + 1)
        return result

class Solution1:
    def rotate(self, nums: list[int], k: int) -> None:
        if len(nums) > 1:
            k %= len(nums)
            nums[:-k], nums[-k:] = nums[-k:], nums[:-k]


class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        def reverse(start, stop):
            for i in range((stop - start) // 2):
                l, r = start + i, stop - 1 - i
                nums[l], nums[r] = nums[r], nums[l]

        k %= len(nums)
        reverse(0, len(nums) - k)
        reverse(len(nums) - k, len(nums))
        reverse(0, len(nums))

from collections import Counter


class Solution:
    def minDeletions(self, s: str) -> int:
        result = 0
        used: set[int] = set()
        for c in Counter(s).values():
            while c and c in used:
                result += 1
                c -= 1
            used.add(c)
        return result

class Solution:
    def groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
        ht: dict[int, list[int]] = {}
        for i, s in enumerate(groupSizes):
            ht[s] = ht.get(s, [])
            ht[s].append(i)
        result = []
        for s, l in ht.items():
            result.extend([l[i : i + s] for i in range(0, len(l), s)])
        return result

class Solution:
    def numberOfEmployeesWhoMetTarget(self, hours: list[int], target: int) -> int:
        return sum(1 for x in hours if x >= target)

class Solution:
    def countCompleteSubarrays(self, nums: list[int]) -> int:
        amt, D, result, i = {}, len(set(nums)), 0, 0
        for num in nums:
            amt[num] = amt.get(num, 0) + 1
            while len(amt) == D:
                amt[nums[i]] -= 1
                if amt[nums[i]] == 0:
                    del amt[nums[i]]
                i += 1
            result += i
        return result

class Solution:
    def accountBalanceAfterPurchase(self, purchaseAmount: int) -> int:
        return 100 - (purchaseAmount + 5) // 10 * 10

from ..notes import gcd


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertGreatestCommonDivisors(self, head: ListNode) -> ListNode:
        node = head
        while node.next:
            node.next = ListNode(val=gcd(node.val, node.next.val), next=node.next)
            node = node.next.next
        return head

class Solution:
    def finalString(self, s: str) -> str:
        buf = []
        for c in s:
            if c == 'i':
                buf = buf[::-1]
            else:
                buf.append(c)
        return ''.join(buf)

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        ht: dict[int, list[int]] = {}
        result = -1
        for num in nums:
            tmp, max_digit = num, 0
            while tmp:
                tmp, max_digit = tmp // 10, max(max_digit, tmp % 10)
            ht[max_digit] = sorted(ht.get(max_digit, []) + [num])[-2:]
            if len(ht[max_digit]) == 2:
                result = max(result, sum(ht[max_digit]))
        return result

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [0] + [0xFFFFFFFF] * (amount)
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return (dp[-1], -1)[dp[-1] == 0xFFFFFFFF]

class Solution1:
    def getSum(self, a: int, b: int) -> int:
        MASK, xor, carry = 1023, a ^ b, (a & b) << 1
        if carry & MASK:
            return self.getSum(xor, carry)
        return xor & MASK if carry else xor


class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 1023
        while b & MASK:
            a, b = a ^ b, (a & b) << 1
        return a & MASK if b else a

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        for i in range(len(text1)):
            for j in range(len(text2)):
                if text1[i] == text2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
        return dp[-1][-1]

class Solution:
    def maxArea(self, height: list[int]) -> int:
        result = 0
        l, r = 0, len(height) - 1
        while l != r:
            result = max(result, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result

class Solution:
    def threeSum(self, nums: list[int]):
        result = set()
        zero, neg, pos = counters = {}, {}, {}
        for num in nums:
            counter = counters[(num > 0) + (num != 0)]
            counter[num] = counter.get(num, 0) + 1
        # 0,0,0
        if zero.get(0, 0) >= 3:
            result.add((0, 0, 0))
        # -,+,?
        for n in neg:
            for p in pos:
                target: int = -(n + p)
                counter = counters[(target > 0) + (target != 0)]
                if target in counter:
                    triplet = tuple(sorted([n, p, target]))
                    if target in (n, p):  # duplicate
                        if counter[target] >= 2:
                            result.add(triplet)
                    else:
                        result.add(triplet)
        return result

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)
        target_is_rotated = target < nums[0]
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            mid_is_rotated = nums[mid] < nums[0]
            if (mid_is_rotated, target_is_rotated) == (True, False):  # [t] [m]
                hi = mid
            elif (mid_is_rotated, target_is_rotated) == (False, True):  # [m] [t]
                lo = mid + 1
            # same side
            elif nums[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return -1


class Solution1:
    def search(self, nums: list[int], target: int) -> int:
        # https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/14435/clever-idea-making-it-simple/
        lo, hi = 0, len(nums)
        target_is_rotated = target < nums[0]
        inf = (-1) ** target_is_rotated * float('inf')
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            mid_is_rotated = nums[mid] < nums[0]
            if (nums[mid], inf)[mid_is_rotated != target_is_rotated] > target:
                hi = mid
            else:
                lo = mid + 1
        return -1

class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= nums[-1]:
                hi = mid
            else:
                lo = mid + 1
        return nums[lo]

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        result = acc = nums[0]
        for i in range(1, len(nums)):
            acc = max(nums[i], nums[i] + acc)
            result = max(result, acc)
        return result

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        result = acc_max = acc_min = nums[0]
        for i in range(1, len(nums)):
            cand = nums[i], nums[i] * acc_max, nums[i] * acc_min
            acc_max, acc_min = max(cand), min(cand)
            result = max(result, acc_max, acc_min)
        return result

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        result = [1] * len(nums)
        l = r = 1
        for i in range(len(nums)):
            result[i] *= l
            l *= nums[i]
            result[-1 - i] *= r
            r *= nums[-1 - i]
        return result

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        lo, hi = 0, M * N
        while lo < hi:
            mid = (lo + hi) // 2
            row, col = divmod(mid, N)
            if matrix[row][col] == target:
                return True
            if matrix[row][col] > target:
                hi = mid
            else:
                lo = mid + 1
        return False


class Solution1:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        lo, hi = 0, M
        while lo < hi:
            mid = (lo + hi) // 2
            if matrix[mid][0] == target:
                return True
            if matrix[mid][0] > target:
                hi = mid
            else:
                lo = mid + 1
        row = matrix[lo - 1]
        lo, hi = 0, N
        while lo < hi:
            mid = (lo + hi) // 2
            if row[mid] == target:
                return True
            if row[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return False