def test_1():
    n = int(input())
    array1 = input().split(" ")
    m = int(input())
    array2 = input().split(" ")
    array1 = [int(num) for num in array1]
    array2 = [int(num) for num in array2]
    index1 = 0
    index2 = 0
    ans = []
    while index1 < len(array1) and index2 < len(array2):
        if array1[index1] == array2[index2]:
            ans.append(str(array1[index1]))
            index1 += 1
            index2 += 1
        elif array1[index1] > array2[index2]:
            index1 += 1
        else:
            index2 += 1
    print(" ".join(ans))

def test_2():
    tmp = input().split(" ")
    n = int(tmp[0])
    m = int(tmp[1])
    team_dict = [[] for _ in range(n + 1)]
    teams = []
    for i in range(m):
        tmp = input().split(" ")[1:]
        tmp = [int(num) for num in tmp]
        teams.append(tmp)
        for p_num in tmp:
            team_dict[p_num].append(i)
    stack = [0]
    visited = [False] * m
    informed = [False] * (n + 1)
    informed[0] = True
    index = 0
    while index < len(stack):
        tmp_p = stack[index]
        tmp_team = team_dict[tmp_p]
        for team_num in tmp_team:
            if visited[team_num]:
                continue
            for person in teams[team_num]:
                if informed[person]:
                    continue
                stack.append(person)
                informed[person] = True
            visited[team_num] = True
        index += 1
    print(informed.count(True))

def test_3():
    tmp = input().split(" ")
    n = int(tmp[0])
    k = int(tmp[1])
    str_dict = {}
    for _ in range(n):
        tmp = input()
        str_dict[tmp] = str_dict.get(tmp, 0) + 1
    tmp_list = []
    for key in str_dict.keys():
        tmp_list.append((key, str_dict[key]))
    list2 = sorted(tmp_list, key=lambda x: [x[1], x[0]])
    list1 = sorted(tmp_list, key=lambda x: [-x[1], x[0]])
    for i in range(k):
        print(list1[i][0], list1[i][1])
    for i in range(k):
        print(list2[i][0], list2[i][1])

def test_4():
    n = int(input())
    nums = input().split(" ")
    index_nums = []
    for i in range(len(nums)):
        index_nums.append((i, int(nums[i])))
    order_nums = sorted(index_nums, key=lambda x: [x[1], x[0]])
    indexs = [0] * n
    for i in range(len(order_nums)):
        indexs[order_nums[i][0]] = i
    for i in indexs:
        if i > n / 2 - 1:
            print(order_nums[n // 2 - 1][1])
        else:
            print(order_nums[n // 2][1])
    return