#Problem P01. [算法课分治] 最大二叉树
#给定一个不含重复元素的整数数组,以此数组直接递归构建的最大二叉树

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)

#Problem P02. [算法课分治] 寻找多数
#给定一个大小为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)

#Problem P03. [算法课分治] 找到最大子序和
#给定一个整数数组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)

#Problem P06. [算法课动态规划] 换硬币
#给定面值分别为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)

#Problem P07. [算法课动态规划]走网格 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))

#Problem P08. [算法课动态规划]爬楼梯
#假设你正在爬楼梯。需要爬 n 阶你才能到达楼顶（n 是正整数）。每次你可以爬 1 或 2 个台阶。你有多#少种不同的方法可以爬到楼顶呢？

n = int(input())
a, b = 1, 2
for _ in range(n - 1):
    a, b = b, a + b
print(a)

#Problem P09. [算法课动态规划]背包问题
#一个背包有一定的承重c，有 N 件物品。设数组下标从 1 开始。
#每件物品都有自己的价值，记录在数组 V 中，也都有自己的重量，记录在数组 W 中，
#每件物品只能选择要装入还是不装入背包，要求在不超过背包承重的前提下，选出的物品总价值最大。
#输出能装入背包的物品的最大总价值。

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])

#Problem P10. [算法课动态规划]最长回文子串
#求一个字符串中的最长的回文子串
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])

#Problem P14. [算法课回溯]目标和
#给你一个整数数组 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])

#Problem P15. [算法课回溯] 电话号码的字母组合
#给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案按字母顺序返回。
#给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

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("'", ""))

#Problem P16. [算法课回溯]优美的排列
#假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），
#只要满足下述条件之一，该数组就是一个优美的排列。
#perm[i] 能够被 i 整除;i 能够被 perm[i] 整除
#给你一个整数 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)

#Problem P17. [算法课分支限界法]组合
#给定两个整数 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, [])

#Problem P21. [算法课动态规划] 整数拆分
#给定一个正整数 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))

#Problem P25. [算法课分治] 找假币
#给你一个装有 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))

#Problem P29. [算法课分支限界法]分割等和子集
#给定一个非空的正整数数组 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")

#Problem P32. [算法课贪婪]三角形的最大周长
#给定由一些正数（代表长度）组成的数组 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)