##1.给定一个不含重复元素的整数数组 nums以此数组直接递归构建的最大二叉树
nums = input().split(' ')
res = []
def fun(lst:list):
    global res
    if lst == []:
        res.append('null')
    else:
        m = max(lst)
        i = lst.index(m)
        res.append(str(m))
        if len(lst)>1:
            fun(lst[0:i])
            fun(lst[i+1:])

nums = [int(n) for n in nums]
fun(nums)
print(' '.join(res))

def create(nums):
    if not nums:
        return
    i = nums.index(max(nums))
    print(nums.pop(i),end=' ')
    if i==0 and nums:
        print('null',end=' ')
        create(nums)
    elif i==len(nums) and nums:
        create(nums)
        print("null",end=' ')
    else:
        create(nums[:i])
        create(nums[i:])
b=[]
for i in input().split():
    b.append(int(i))
create(b)

##给定一个大小为n的整型数组a，找到其中的多数元素，多数元素是指在数组中出现次数大于⌊n/2⌋的元素。
n = int(input())
a = list(map(int, input().split()))
candidate = a[0]
count = 1
for num in a[1:]:
    if num == candidate:
        count += 1
    else:
        count -= 1
        if count == 0:
            candidate = num
            count = 1
print(candidate)

##给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
n = int(input())
nums = list(map(int, input().split()))
if not nums:
    print(0)
else:
    current_sum = max_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    print(max_sum)

##给定面值分别为2，5，7的硬币，每种硬币有无限个，给定一个N，求组成N最少需要的硬币的数量，若无法组成则返回-1.
N = int(input())
coins = [2, 5, 7]
dp = [float('inf')] * (N + 1)
dp[0] = 0
for i in range(1, N + 1):
    for coin in coins:
        if i >= coin:
            dp[i] = min(dp[i], dp[i - coin] + 1)
print(dp[N] if dp[N] != float('inf') else -1)

##m行n列的网格，从左上角(1,1)出发，每一步只能向下或者向右，问共有多少种方法可以走到右下角(m,n)
import math
def calculate_paths(m, n):
    return math.comb(m+n-2, m-1)
m, n = map(int, input().split())
print(calculate_paths(m, n))

##假设你正在爬楼梯。需要爬n阶你才能到达楼顶（n是正整数）。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
n = int(input())
a, b = 1, 2
for _ in range(n - 1):
    a, b = b, a + b
print(a)

##要求在不超过背包承重的前提下，选出的物品总价值最大。输出能装入背包的物品的最大总价值。
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])

##求一个字符串中的最长的回文子串
s = input().strip()
n = len(s)
if n < 2:
    print(s)
    exit()
start, max_len = 0, 1
def expand_around_center(left, right):
    while left >= 0 and right < n and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1
for i in range(n):
    len1 = expand_around_center(i, i)
    len2 = expand_around_center(i, i + 1)
    current_max = max(len1, len2)
    if current_max > max_len:
        max_len = current_max
        start = i - (max_len - 1) // 2
print(s[start:start + max_len])

##给你一个整数数组 nums 和一个整数 target ，向数组中的每个整数前添加'+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式
nums = list(map(int, input().split()))
target = int(input())

total = sum(nums)
if (total + target) % 2 != 0 or total < abs(target):
    print(0)
else:
    p = (total + target) // 2
    dp = [0] * (p + 1)
    dp[0] = 1
    for num in nums:
        for i in range(p, num - 1, -1):
            dp[i] += dp[i - num]
    print(dp[p])

##给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案按字母顺序返回。
import itertools
def letter_combinations(digits):
    if not digits:
        return []
    digit_map = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }
    letters = [digit_map[d] for d in digits]
    products = itertools.product(*letters)
    result = [''.join(p) for p in products]
    result.sort()
    return result
digits = input().strip()
combinations = letter_combinations(digits)
print(str(combinations).replace("'", ""))

##假设有从 1 到 n 的 n 个整数，给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
n = int(input())
count = 0

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

used = [False] * (n + 1)
backtrack(1, used)
print(count)

##给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
n, k = map(int, input().split())

def backtrack(start, path):
    if len(path) == k:
        print(' '.join(map(str, path)))
        return
    for i in range(start, n + 1):
        path.append(i)
        backtrack(i + 1, path)
        path.pop()

backtrack(1, [])

##给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。
def integerBreak(n):
    if n == 2:
        return 1
    if n == 3:
        return 2
    product = 1
    while n > 4:
        product *= 3
        n -= 3
    product *= n
    return product
n = int(input())
print(integerBreak(n))

##给你一个装有n枚硬币的袋子。其中有一枚硬币是伪造的，并且伪造的硬币比真的硬币要轻一些。用一个整型数组a代表硬币的重量。 你的任务是找出这枚伪造的硬币。
n = int(input())
a = list(map(int, input().split()))

def find_fake(start, end):
    if start == end:
        return start + 1  # 返回位置（从1开始）
    size = end - start + 1
    group_size = (size + 2) // 3  # 确保分组合理
    # 分成三组：g1, g2, g3
    g1_end = start + group_size - 1
    g2_end = g1_end + group_size
    # 比较前两组的重量
    sum1 = sum(a[start:g1_end + 1])
    sum2 = sum(a[g1_end + 1:g2_end + 1])
    if sum1 < sum2:
        return find_fake(start, g1_end)
    elif sum1 > sum2:
        return find_fake(g1_end + 1, g2_end)
    else:
        return find_fake(g2_end + 1, end)

print(find_fake(0, n - 1))

##给定一个非空的正整数数组 nums(nums.length < 5) ，请判断能否将这些数字分成元素和相等的两部分
nums = list(map(int, input().split()))
total = sum(nums)
if total % 2 != 0:
    print("false")
else:
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    print("true" if dp[target] else "false")

##给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0。
A = list(map(int, input().split()))
A.sort()
n = len(A)
max_perimeter = 0
for i in range(n - 1, 1, -1):
    if A[i - 2] + A[i - 1] > A[i]:
        max_perimeter = A[i - 2] + A[i - 1] + A[i]
        break
print(max_perimeter)