2026-01-09 13:31:31 +0300 MSK

import functools

class Solution:
    def findMin(self, nums: List[int]) -> int:
        length = len(nums)
        if length < 3:
            return min(nums)
        inf = float("inf")

        @functools.cache
        def check(i: int) -> int:
            if i == 0:
                prev, nxt = length - 1, 1
            elif i == length - 1:
                prev, nxt = length - 2, 0
            else:
                prev, nxt = i - 1, i + 1
            num_prev, num_cur, num_nxt = nums[prev], nums[i], nums[nxt]
            if num_cur < num_prev:
                return num_cur
            if num_nxt < num_cur:
                return num_nxt
            return -1

        @functools.cache
        def dp(left: int, right: int) -> int:
            if left < 0 or right == length or left > right:
                return  inf
            mid = left + (right - left) // 2
            num_left, num_mid, num_right = nums[left], nums[mid], nums[right]
            for idx in (left, mid, right):
                check_res = check(idx)
                if check_res != -1:
                    return check_res
            if num_left == num_mid == num_right:
                return min(num_left, dp(left + 1, mid - 1), dp(mid + 1, right - 1))
            if num_mid < num_left:
                return dp(left + 1, mid - 1)
            return dp(mid + 1, right - 1)
        
        return dp(0, length - 1)