def check(buildings, idx):
    l = idx - 2 if idx >= 2 else 0
    r = idx + 3

    sides = buildings[l : idx] + buildings[idx + 1 : r]
    side_max = max(sides)

    height = buildings[idx]

    if height - side_max > 0:
        return height - side_max
    else:
        return 0

T = 10
for t in range(1, T + 1):
    n = int(input().strip())
    buildings = list(map(int, input().split()))

    total = 0
    for idx in range(n):
        total += check(buildings, idx)

    print(f'#{t} {total}')

T = int(input())

mirror = {
    'b': 'd',
    'd': 'b',
    'p': 'q',
    'q': 'p'
}

for t in range(1, T+1):
    word = input()

    result = ''
    for i in range(len(word) - 1, -1, -1):
        result += mirror[word[i]]

    print('#{} {}'.format(t, result))

T = int(input())

for t in range(1, T+1):
    N, K = map(int, input().split())
    MAP = [[0 for _ in range(N+2)] for _ in range(N+2)]

    for i in range(1, N+1):
        MAP[i][1:-1] = map(int, input().split())

    cnt_list = [0 for _ in range(N + 1)]
    for i in range(1, N+1):
        # row
        j = 1
        while j <= N:
            cnt = 0
            while MAP[i][j]:
                cnt += 1
                j += 1
            cnt_list[cnt] += 1
            j += 1

        # col
        j = 1
        while j <= N:
            cnt = 0
            while MAP[j][i]:
                cnt += 1
                j += 1
            cnt_list[cnt] += 1
            j += 1


    print('#{} {}'.format(t, cnt_list[K]))

방법 1) bubble sort

def bubble_sort(lst):
    for i in range(1, len(lst)):
        for j in range(len(lst) - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        bubble_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 2) selection sort

def selection_sort(lst):
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        selection_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 3) merge sort

def merge_sort(lst, l, r):
    if r - l <= 1:
        return

    c = (l + r) // 2

    merge_sort(lst, l, c)
    merge_sort(lst, c, r)

    l_ptr = l
    r_ptr = c
    tmp_lst = []
    while l_ptr < c and r_ptr < r:
        if lst[l_ptr] < lst[r_ptr]:
            tmp_lst.append(lst[l_ptr])
            l_ptr += 1
            continue
        else:
            tmp_lst.append(lst[r_ptr])
            r_ptr += 1

    while l_ptr < c:
        tmp_lst.append(lst[l_ptr])
        l_ptr += 1

    while r_ptr < r:
        tmp_lst.append(lst[r_ptr])
        r_ptr += 1

    for tmp_i, i in enumerate(range(l, r)):
        lst[i] = tmp_lst[tmp_i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        merge_sort(lst, 0, len(lst))

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

T = 10

for t in range(1, T+1):
    int(input())
    MAP = [[0 for _ in range(102)] for _ in range(100)]
    for i in range(100):
        MAP[i][1:-1] = map(int, input().split())

    start_j = 0
    for j in range(1, 101):
        if MAP[99][j] == 2:
            start_j = j
            break

    i = 99
    j = start_j
    while i:
        if MAP[i][j + 1]:
            while MAP[i][j + 1]:
                j += 1
            i -= 1
        elif MAP[i][j - 1]:
            while MAP[i][j - 1]:
                j -= 1
            i -= 1
        else:
            i -= 1

    result = j - 1
    print('#{} {}'.format(t, result))

T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    MAP = []
    for i in range(N):
        MAP.append(list(map(int, input().split())))

    total_map = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            total_map[i][j] = MAP[i - 1][j - 1] + total_map[i - 1][j] + total_map[i][j - 1] - total_map[i - 1][j - 1]

    result = total_map[M][M]
    for i in range(M, N + 1):
        for j in range(M, N + 1):
            total = total_map[i][j] - total_map[i - M][j] - total_map[i][j - M] + total_map[i - M][j - M]
            if total > result:
                result = total

    print('#{} {}'.format(t, result))

T = 10

for t in range(1, T+1):
    lst = []
    _ = int(input())
    for i in range(100):
        lst.append(list(map(int, input().split())))

    max = 0
    for i in range(100):
        max += lst[0][i]


    for i in range(100):
        total = 0
        for j in range(100):
            total += lst[i][j]
        if max < total:
            max = total

    for j in range(100):
        total = 0
        for i in range(100):
            total += lst[i][j]
        if max < total:
            max = total

    total = 0
    for i in range(100):
        total += lst[i][i]

    if max < total:
        max = total

    total = 0
    for i in range(100):
        total += lst[99 - i][i]

    if max < total:
        max = total

    print('#{} {}'.format(t, max))

T = int(input())

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

for t in range(1, T+1):
    n = int(input())

    lst = [[0 for _ in range(n+2)] for _ in range(n+2)]

    for i in range(1, n+2):
        lst[0][i] = -1
        lst[n + 1][i] = -1
        lst[i][0] = -1
        lst[i][n + 1] = -1

    i = 1
    j = 0
    num = 1
    d = 0
    while num <= n*n:
        next_i = i + di[d]
        next_j = j + dj[d]

        if lst[next_i][next_j]:
            d = (d + 1) % 4
            continue

        i = next_i
        j = next_j
        lst[i][j] = num
        num += 1

    print('#{}'.format(t))
    for i in range(1, n+1):
        print(*lst[i][1:n+1], sep=' ')