By the triangle inequality, for all real numbers x, y, z, we have: |x − y| + |y − z| ≥ |x − z| with equality if and only if min(x, z) ≤ y ≤ max(x, z).

Now, take indices i and j such that $$$a_i$$$ and $$$a_j$$$ are the maximum and minimum values of the array, respectively. Then, for each index k, we have $$$a_i$$$≥$$$a_k$$$≥$$$a_j$$$, meaning that |$$$a_i$$$−$$$a_k$$$| + |$$$a_k$$$−$$$a_j$$$| = $$$a_i$$$−$$$a_k$$$+$$$a_k$$$−$$$a_j$$$ = $$$ai$$$−$$$aj$$$ = |$$$ai$$$−$$$aj$$$|, as we desired.

t = int(input())
for _ in range(t):
    n = int(input())
    minv, maxv = 1e9 + 1, -1
    mini = maxi = 0

    for i in range(n):
        a = int(input())
        if a > maxv:
            maxi = i + 1
            maxv = a
        if a < minv:
            mini = i + 1
            minv = a
    print(mini, maxi)

Make a copy of the array s: call it t. Sort t in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all i such that $$$s_i$$$≠$$$t_1$$$, we should output $$$s_i$$$−$$$t_1$$$. Otherwise, output $$$s_i$$$−$$$t_2$$$ — the second highest strength, which is the next best person.

t = int(input())

for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = sorted(a)
    for i in range(n):
        if a[i] == b[n - 1]:
            print(a[i] - b[n - 2], end=" ")
        else:
            print(a[i] - b[n - 1], end=" ")
    print()

To solve the problem, it was enough to count the number of planets with the same orbits $$$cnt_i$$$ and sum up the answers for the orbits separately. For one orbit, it is advantageous either to use the second machine once and get the cost c, or to use only the first one and get the cost equal to $$$cnt_i$$$.

from collections import defaultdict

t = int(input())

for _ in range(t):
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = defaultdict(int)
    ans = 0
    for i in range(n):
        cnt[a[i]] += 1
        if cnt[a[i]] <= c:
            ans += 1
    print(ans)
}

Let's sort the arrays first.

Let's check the two smallest elements in the arrays and investigate their behavior. First, obviously, if $$$a_1$$$+1<$$$b_1$$$ (as nothing can be matched with $$$a_1$$$) or $$$a_1$$$>$$$b_1$$$ (as nothing can be matched with $$$b_1$$$) the answer is No. Then, it's possible that $$$a_1$$$=$$$b_1$$$=x. In this case, we have to have at least one x in the array a at the end. Hence, we can leave $$$a_1$$$ untouched, as it already suits to $$$b_1$$$. It's also possible that $$$a_1$$$+1=$b_1$. Here we have to increase $$$a_1$$$ by 1. In both cases, the task is reduced to the smallest one.

Going to the exact solution from this logic, we just have to sort both arrays and check that for each 1≤i≤n it's $$$a_i$$$=$$$b_i$$$ or $$$a_i$$$+1=$b_i$.

The complexity of the solution is O(nlog(n)).

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort()
    ok = True
    for i in range(n):
        if a[i] + 1 != b[i] and a[i] != b[i]:
            ok = False
            break
    print("YES" if ok else "NO")

Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights.

Solution complexity: O(n), since we can sort by counting.

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

a.sort()

for i in a:
    print(i, end=' ')