def sort_b2s(nums, left, right):
    if left >= right: return
    i, j= left, right
    while i < j:
        while nums[j] > nums[left] and i < j: j -= 1
        while nums[i] <= nums[left] and i < j: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[left] = nums[left], nums[i]
    sort_b2s(nums, left, i - 1)
    sort_b2s(nums, i + 1, right)

def search_left(nums, left, right, x):
    while left < right:
        mid = left + right >> 1
        if nums[mid] >= x:
            right = mid
        else:
            left = mid + 1
    return left


def search_right(nums, left, right, x):
    while left < right:
        mid = left + right + 1 >> 1
        if nums[mid] > x:
            right = mid - 1
        else:
            left = mid
    return left

curs = [0]
for n in nums:
    curs.append(curs[-1] + n)

left, right, res, nums_len = -k - 1, k - 1, [], len(nums)
        
for _ in range(nums_len):
    left += 1
    right += 1
    if left >= 0 and right < nums_len:
        cur = curs[right + 1] - curs[left]
        res.append(cur // (2 * k + 1))
    else:
        res.append(-1)

if not s: return 0
res, bi, left, right = 1, set(), 0, 0
bi.add(s[0])
for i in range(1, len(s)):
    right += 1
    if s[i] in bi:
        while left <= right:
            if s[left] != s[i]:
                bi.remove(s[left])
                left += 1
            else:
                left += 1
                break
    bi.add(s[i])
    
    res = max(right - left + 1, res)
return res

len_1, len_2 = len(nums1), len(nums2)
len_1a2 = len_1 + len_2
mid = len_1a2 >> 1

l1, l2 = 0, 0
s, m = 0, 0
while mid >= 0:
    if l1 < len_1 and l2 < len_2:
        if nums1[l1] > nums2[l2]:
            cur = nums2[l2]
            l2 += 1
        else:
            cur = nums1[l1]
            l1 += 1
    elif l1 < len_1:
        cur = nums1[l1]
        l1 += 1
    else:
        cur = nums2[l2]
        l2 += 1
    s, m = m, cur
    mid -= 1
return float(s + m) / 2 if not len_1a2 % 2 else float(m)

def longestPalindrome(s):
    def expend_substr(left, right):
        while left >= 0 and right < s_l and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    
    # 最终回文的始终
    start, end, s_l = 0, 0, len(s)
    for i in range(s_l):
        # 偶数回文
        left, right = expend_substr(i, i + 1)

        if right - left > end - start:
            start, end = left, right

        # 奇数回文
        left, right = expend_substr(i, i)

        if right - left > end - start:
            start, end = left, right
    
    return s[start: end + 1]

def longestPalindrome(s):
    s_len = len(s)
    if s_len < 2:
        return s
    dp = [[False] * s_len for _ in range(s_len)]
    for i in range(s_len):
        dp[i][i] = True
    
    max_len, start = 1, 0
    # 回文长度
    for l in range(2, s_len + 1):
        # 回文字符起始位置
        for st in range(s_len):
            ed = l + st - 1
            if ed >= s_len:
                break
            if s[st] != s[ed]:
                dp[st][ed] = False
            else:
                if l <= 3:
                    dp[st][ed] = True
                else:
                    dp[st][ed] = dp[st + 1][ed - 1]
            
            if dp[st][ed] and l > max_len:
                max_len = l
                start = st
    return s[start: start + max_len]