#1.最大二叉树 class TreeNode:

def __init__(self,val=0,left=None,right=None):
    self.val = val
    self.left = left
    self.right = right

def MaxTree(nums):

if not nums:
    return None

max_val=max(nums)
max_index=nums.index(max_val)

root = TreeNode(max_val)

root.left = MaxTree(nums[:max_index])
root.right = MaxTree(nums[max_index+1:])

return root

def print_tree(root: TreeNode):

if not root:
    print("null", end=" ")
    return

else:
    print(root.val, end=" ")
if not root.left and not root.right:
    return

else:
    print_tree(root.left)
    print_tree(root.right)

nums = list(map(int,input().split())) root = MaxTree(nums) print_tree(root) #2.寻找多数 def result(len,nums):

if not nums:
    return

index=nums[0]
sums=1
for i in nums[1:len-1]:
    if index == i:
        sums+=1
    else:
        sums-=1
    if sums == 0:
        index = i
        sums = 1
print(index)

len= int(input()) nums = [int(x) for x in input().split()] result(len,nums) #3.最大子序和 def max_subarray_sum(nums):

"""
计算最大子数组和
"""
# 初始化
max_sum = current_sum = nums[0]

# 遍历数组（从第二个元素开始）
for num in nums[1:]:
    # 关键决策：是重新开始还是延续当前子数组
    current_sum = max(num, current_sum + num)
    # 更新全局最大值
    max_sum = max(max_sum, current_sum)

return max_sum

n = int(input()) nums = list(map(int, input().split())) print(max_subarray_sum(nums)) #4.k个最小数 def quicksort(nums):

if len(nums) <= 1 :
    return nums
else:
    pivot = nums[0]
    left = [x for x in nums[1:] if x < pivot]
    right = [x for x in nums[1:] if x >= pivot]
    return quicksort(left) + [pivot] + quicksort(right)

def result(k,nums):

for i in range (k):
    print(nums[i],end=" ")

n,k= map(int,input().split()) nums = [int(x) for x in input().split()] sort_nums=quicksort(nums)

result(k,sort_nums) #5.k个最大元素 def quicksort(nums):

if len(nums) <= 1 :
    return nums
else:
    pivot = nums[0]
    left = [x for x in nums[1:] if x > pivot]
    right = [x for x in nums[1:] if x <= pivot]
    return quicksort(left) + [pivot] + quicksort(right)

n,k= map(int,input().split()) nums = [int(x) for x in input().split()] sort_nums=quicksort(nums) print(sort_nums[k-1]) #6.k个最长重复字符串 def longest_substring(s, k):

if len(s) < k: return 0
from collections import Counter
cnt = Counter(s)

for c in s:
    if cnt[c] < k:
        return max(longest_substring(p, k) for p in s.split(c))

return len(s)

import sys

s, k = sys.stdin.read().split() print(longest_substring(s, int(k)))

#7.链表排序 class ListNode:

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

def sort_list(head):

if not head or not head.next:
    return head
# 快慢指针找中点
slow, fast = head, head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

mid = slow.next
slow.next = None
# 归并排序
return merge(sort_list(head), sort_list(mid))

def merge(a, b):

dummy = cur = ListNode()
while a and b:
    if a.val < b.val:
        cur.next = a
        a = a.next
    else:
        cur.next = b
        b = b.next
    cur = cur.next
cur.next = a or b
return dummy.next

import sys

nums = list(map(int, sys.stdin.read().split()))

if nums:

# 构建链表
head = ListNode(nums[0])
cur = head
for x in nums[1:]:
    cur.next = ListNode(x)
    cur = cur.next

# 排序
head = sort_list(head)

# 输出
res = []
while head:
    res.append(str(head.val))
    head = head.next
print(' '.join(res))

#8.柠檬水 def charge(bills):

key=1
if bills[0]!=5:
    key=0
else:
    five=1
    ten=0
    for i in bills[1:]:
        if i == 5:
            five+=1
        elif i ==10:
            if five <1:
                key=0
            else:
                five -=1
                ten +=1
        else:
            if (ten>=1 and five>=1) :
                ten-=1
                five-=1
            elif ten==0 and five>=3:
                five-=3
            else:
                key=0
if key==0:
    print("false")
else:
    print("true")

bills = [int(x) for x in input().split()] charge(bills) #9.换硬币 def boin(n):

sum = 50
key=0
for i in range(15):
    for j in range(20):
        for k in range(50):
            if i*7+j*5+k*2==n and i+j+k<sum:
                sum=i+j+k
                key=1
if key==0:
    print(-1)
else:
    print(sum)

n=int(input()) boin(n) #10.走网格

import math m, n = map(int, input().split()) print(math.comb(m + n - 2, m - 1))

#11.6和9 def turnmax(num):

# 将数字转为字符串处理更方便
num_str = str(num)

# 找到第一个6的位置，替换为9
for i in range(len(num_str)):
    if num_str[i] == '6':
        # 替换第一个6为9
        result = num_str[:i] + '9' + num_str[i + 1:]
        print(int(result))
        return

# 如果没有6，直接输出原数字
print(num)

num = int(input()) turnmax(num)

#12.括号生成 import sys

def generate_parenthesis(n: int):

res = []
def backtrack(path, left, right):
    if left == n and right == n:
        res.append("".join(path))
        return
    if left < n:
        path.append("(")
        backtrack(path, left + 1, right)
        path.pop()
    if right < left:
        path.append(")")
        backtrack(path, left, right + 1)
        path.pop()
backtrack([], 0, 0)
return res

def main():

data = sys.stdin.read().strip().split()
if not data:
    print("[]")
    return
n = int(data[0])
if n <= 0:
    print("[]")
    return
ans = generate_parenthesis(n)
print("[" + ", ".join(ans) + "]")

if __name__ == "__main__":

main()

#13.组合问题 def combine(n, k):

def backtrack(start, path):
    if len(path) == k:
        result.append(path[:])  # 添加当前组合的副本
        return
    for i in range(start, n + 1):
        path.append(i)
        backtrack(i + 1, path)
        path.pop()

result = []
backtrack(1, [])
return result

n, k = map(int, input().split()) combinations = combine(n, k)

print(combinations) #14.计算所有子集异或值的总和 def subset_xor_sum(nums):

"""
计算所有子集异或值的总和
"""
n = len(nums)
total = 0

def backtrack(index, current_xor):
    nonlocal total

    # 当前子集的异或值
    total += current_xor

    # 继续添加元素
    for i in range(index, n):
        # 选择 nums[i]
        backtrack(i + 1, current_xor ^ nums[i])
        # 回溯：不选择 nums[i] 已经在循环中处理

backtrack(0, 0)
return total

nums = list(map(int, input().split())) print(subset_xor_sum(nums))

#15.分割回文串 def partition(s):

n = len(s)
res = []

def dfs(start, path):
    if start == n:
        res.append(path[:])
        return
    for end in range(start, n):
        sub = s[start:end + 1]
        if sub == sub[::-1]:
            path.append(sub)
            dfs(end + 1, path)
            path.pop()

dfs(0, [])
return res

s = input().strip()

result = partition(s)

if not result:

print("[]")

else:

formatted = []
for part in result:
    formatted.append("[" + ", ".join(part) + "]")
print("[" + ", ".join(formatted) + "]")

#16.目标和 def find_target_sum_ways(nums, target):

total = sum(nums)

# 不可能的情况
if abs(target) > total or (target + total) % 2:
    return 0

# 计算需要凑的正数和
pos_sum = (target + total) // 2

# dp数组
dp = [0] * (pos_sum + 1)
dp[0] = 1

# 背包问题
for num in nums:
    for j in range(pos_sum, num - 1, -1):
        dp[j] += dp[j - num]

return dp[pos_sum]

nums = list(map(int, input().split())) target = int(input()) print(find_target_sum_ways(nums, target))

#17.组合 def combine(n, k):

def backtrack(start, path):
    if len(path) == k:
        result.append(path)
        return
    for i in range(start, n + 1):
        backtrack(i + 1, path + [i])

result = []
backtrack(1, [])
return result

n, k = map(int, input().split()) for comb in combine(n, k):

print(' '.join(map(str, comb)))

#18.大礼包 from functools import lru_cache

lines = [list(map(int, input().split())) for _ in range(4)] # 根据样例固定4行

price, m = lines[0][:-1], lines[0][-1] special = lines[1:3] needs = lines[3]

@lru_cache(None) def f(state):

n = len(price)
# 直接买
cost = sum(price[i] * state[i] for i in range(n))
# 尝试礼包
for p in special:
    new_state = list(state)
    if all(p[i] <= new_state[i] for i in range(n)):
        for i in range(n):
            new_state[i] -= p[i]
        cost = min(cost, p[-1] + f(tuple(new_state)))
return cost

print(f(tuple(needs)))

#19.Equal Sum def can_partition_k_subsets(nums, k):

total = sum(nums)
if total % k != 0:
    return False

target = total // k
nums.sort(reverse=True)

if nums[0] > target:
    return False

n = len(nums)
used = [False] * n

def dfs(start, current_sum, count):
    """
    深度优先搜索

    参数:
        start: 起始索引
        current_sum: 当前子集的和
        count: 已完成的子集数量
    """
    if count == k - 1:  # 最后一个子集自动满足
        return True

    if current_sum == target:
        # 完成一个子集，开始下一个
        return dfs(0, 0, count + 1)

    for i in range(start, n):
        if not used[i] and current_sum + nums[i] <= target:
            used[i] = True
            if dfs(i + 1, current_sum + nums[i], count):
                return True
            used[i] = False

            # 重要剪枝：如果当前数字无法放入，且当前和为0，直接失败
            if current_sum == 0:
                break

            # 跳过相同数字
            while i + 1 < n and nums[i] == nums[i + 1]:
                i += 1

    return False

return dfs(0, 0, 0)

nums = list(map(int,input().split())) k = int(input()) print(str(can_partition_k_subsets(nums, k)).lower())

#20.分割等和子集 def can_partition(nums):

total = sum(nums)

# 如果总和是奇数，不可能平分
if total % 2 != 0:
    return False

target = total // 2

# 初始化dp数组
dp = [False] * (target + 1)
dp[0] = True  # 和为0总是可以

# 遍历每个数字
for num in nums:
    # 从后往前更新，避免重复使用同一个数字
    for j in range(target, num - 1, -1):
        dp[j] = dp[j] or dp[j - num]

return dp[target]

if __name__ == "__main__":

# 注意：输入是像 "15115" 这样的字符串
# 将字符串转换为数字列表
# 例如 "15115" → [1, 5, 1, 1, 5]
nums = list(map(int, input().split()))

# 或者如果输入是空格分隔的数字，用：
# nums = list(map(int, input().split()))

result = can_partition(nums)
print(str(result).lower())  # 输出 true/false

#21.整数拆分 def integer_break(n):

dp = [0] * (n + 1)

# 初始化
dp[1] = 1
dp[2] = 1  # 2 = 1 + 1, 乘积1

# 计算dp[3]到dp[n]
for i in range(3, n + 1):
    # 尝试所有拆分方式
    for j in range(1, i):
        # 不继续拆分 vs 继续拆分
        dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

return dp[n]

n = int(input()) print(integer_break(n))

#22.打家劫舍 def rob(nums):

n = len(nums)
if n == 0:
    return 0
if n == 1:
    return nums[0]

# 初始化dp数组
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

# 状态转移
for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

return dp[-1]

nums = list(map(int, input().split())) print(rob(nums))

#23.戳气球 def max_coins_simple(nums):

# 添加边界气球
nums = [1] + nums + [1]
n = len(nums)

# dp[i][j] 表示戳破 (i, j) 区间内气球的最大得分
dp = [[0] * n for _ in range(n)]

# 区间长度从3开始（因为两端是虚拟气球，实际至少包含1个气球）
for length in range(2, n):  # 注意这里是2，因为开区间(i,j)至少有一个气球时j-i>=2
    for i in range(0, n - length):
        j = i + length
        # 尝试每个位置作为最后一个戳破的
        for k in range(i + 1, j):
            # 最后戳破k：左边得分 + 右边得分 + 戳破k的得分
            score = dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
            dp[i][j] = max(dp[i][j], score)

return dp[0][n - 1]

nums = list(map(int, input().split())) print(max_coins_simple(nums))

#24.三数之和 def three_sum(nums):

nums.sort()
res = []
n = len(nums)

for i in range(n - 2):
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    if nums[i] > 0:
        break

    left, right = i + 1, n - 1
    while left < right:
        total = nums[i] + nums[left] + nums[right]
        if total == 0:
            res.append([nums[i], nums[left], nums[right]])
            while left < right and nums[left] == nums[left + 1]:
                left += 1
            while left < right and nums[right] == nums[right - 1]:
                right -= 1
            left += 1
            right -= 1
        elif total < 0:
            left += 1
        else:
            right -= 1

return res

n = int(input()) nums = list(map(int, input().split())) result = three_sum(nums) out = "[" + ",".join("[" + ",".join(map(str, t)) + "]" for t in result) + "]" print(out)

#25.反转括号 def reverse_parentheses(s):

stack = []
for ch in s:
    if ch == ')':
        # 找到括号内的内容并反转
        temp = []
        while stack[-1] != '(':
            temp.append(stack.pop())
        stack.pop()  # 弹出 '('
        stack += temp
    else:
        stack.append(ch)
return ''.join(stack)

s = input() print(reverse_parentheses(s))

#26.跳跃游戏 def min_jumps(n, nums):

if n <= 1:
    return 0

jumps = 0  # 跳跃次数
current_end = 0  # 当前跳跃能到达的最远位置
farthest = 0  # 所有选择中能到达的最远位置

# 注意：不需要遍历最后一个位置
for i in range(n - 1):
    # 更新能跳到的最远位置
    farthest = max(farthest, i + nums[i])
    # 如果到达当前跳跃的边界
    if i == current_end:
        jumps += 1
        current_end = farthest

        # 如果已经可以到达最后一个位置
        if current_end >= n - 1:
            break
return jumps

n = int(input()) nums = list(map(int, input().split())) print(min_jumps(n, nums))

#27.颜色分类 def color(n,nums):

if not nums:
    return
k=0
key=0
for i in range(k,n):
    if nums[i]==0:
        key=nums[i]
        nums[i]=nums[k]
        nums[k]=key
        k+=1
for i in range(k,n):
    if nums[i]==1:
        key=nums[i]
        nums[i]=nums[k]
        nums[k]=key
        k+=1
# 剩下的2已经在末尾
print("[" + ",".join(map(str, nums)) + "]")

n= int(input()) nums = [int(x) for x in input().split()] color(n,nums) #28.找假币 def find_fake_coin(n, a):

min_weight = min(a)
# 返回第一个最小重量出现的位置（1-based）
for i in range(n):
    if a[i] == min_weight:
        return i + 1

n = int(input()) a = list(map(int, input().split())) print(find_fake_coin(n, a)) #29.最少操作使数组递增 def dizeng():

n=int(input())
nums=list(map(int,input().split()))
k=nums[0]
count=0
for i in range(1,n):
    if nums[i]<=k:
        len=k-nums[i]
        count=count+len+1
        k=nums[i]+len+1
    else:
        k=nums[i]
return count

print(dizeng()) #30.买鸡问题 def buy_chicken(n,k):

key=0
for i in range(100):
    for j in range(100):
        for y in range(0,100,3):
            if (5*i+3*j+y/3==n) and (i+j+y==k):
                print(i,j,y,sep=" ")
                key=1
if key==0:
    print(0)

n,k=map(int,input().split()) buy_chicken(n,k) #31.组合求和 def main():

k, n = map(int, input().split())
res = []

def dfs(start, path, s):
    if len(path) == k:
        if s == n:
            res.append(path.copy())
        return
    for i in range(start, 10):
        if s + i > n:
            break
        path.append(i)
        dfs(i + 1, path, s + i)
        path.pop()
dfs(1, [], 0)
if not res:
    print(0)
else:
    for c in sorted(res, reverse=True):
        print(' '.join(map(str, c)))

if __name__ == "__main__":

main()

#32.完全平方数 def numSquares(n: int):

# 初始化dp数组，dp[i]表示和为i需要的最少平方数
dp = [float('inf')] * (n + 1)
dp[0] = 0

# 遍历1到n
for i in range(1, n + 1):
    # 尝试所有可能的完全平方数
    j = 1
    while j * j <= i:
        dp[i] = min(dp[i], dp[i - j * j] + 1)
        j += 1

return dp[n]

if __name__ == "__main__":

n = int(input().strip())
print(numSquares(n))

#33.饼干 def bingan():

# 读取输入：g是孩子胃口，s是饼干大小
g = list(map(int, input().split()))
s = list(map(int, input().split()))

# 排序：从小到大
g.sort()
s.sort()

child = 0  # 当前孩子的索引
cookie = 0  # 当前饼干的索引
count = 0  # 满足的孩子数量

# 双指针贪心算法
while child < len(g) and cookie < len(s):
    if s[cookie] >= g[child]:
        # 当前饼干可以满足当前孩子
        count += 1
        child += 1  # 下一个孩子
    cookie += 1  # 无论是否满足，都要看下一个饼干

return count

print(bingan())

#34.电话 def letterCombinations(digits: str):

if not digits:
    return []

phone_map = {
    '2': "abc",
    '3': "def",
    '4': "ghi",
    '5': "jkl",
    '6': "mno",
    '7': "pqrs",
    '8': "tuv",
    '9': "wxyz"
}

result = []

def backtrack(index, path):
    if index == len(digits):
        result.append(path)
        return
    for letter in phone_map[digits[index]]:
        backtrack(index + 1, path + letter)

backtrack(0, "")
result.sort()  # 按字母顺序排序
return result

if __name__ == "__main__":

digits = input().strip()
combinations = letterCombinations(digits)

# 按照样例格式输出
output_str = "[" + ", ".join(combinations) + "]"
print(output_str)

#35.优美排列 def countArrangement_backtrack(n: int) -> int:

used = [False] * (n + 1)
count = 0

def backtrack(pos):
    nonlocal count
    if pos > n:
        count += 1
        return
    for num in range(1, n + 1):
        if not used[num]:
            if (num % pos == 0 or pos % num == 0):
                used[num] = True
                backtrack(pos + 1)
                used[num] = False

backtrack(1)
return count

if __name__ == "__main__":

n = int(input().strip())
print(countArrangement_backtrack(n))

#36.背包问题 N, c = map(int, input().split()) W = list(map(int, input().split())) V = list(map(int, input().split()))

dp = [0] * (c + 1)

for i in range(N):

for j in range(c, W[i] - 1, -1):
    dp[j] = max(dp[j], dp[j - W[i]] + V[i])

print(dp[c])

#37.最长回文字 def longestPalindrome(s: str) -> str:

if not s:
    return ""

start = 0
max_len = 1

def expand_around_center(left: int, right: int) -> int:
    """从中心向两边扩展，返回回文长度"""
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

for i in range(len(s)):
    # 奇数长度的回文
    len1 = expand_around_center(i, i)
    # 偶数长度的回文
    len2 = expand_around_center(i, i + 1)

    # 取较长的那个
    curr_len = max(len1, len2)

    if curr_len > max_len:
        max_len = curr_len
        start = i - (curr_len - 1) // 2

return s[start:start + max_len]

if __name__ == "__main__":

s = input().strip()
print(longestPalindrome(s))

#38.连续数组最大和 def result(n,nums):

max_sum=nums[0]
current_sum=nums[0]
for i in range(n):
    current_sum = max(nums[i],current_sum+nums[i])

    max_sum = max(max_sum,current_sum)

return max_sum

n=int(input()) nums=list(map(int,input().split()))

print(result(n,nums))