1. Идея

Нужно упорядочить все числа массива по неубыванию, то есть так, чтобы каждое следующее число было не меньше предыдущего.

Это классическая задача на сортировку: читаем массив, сортируем его стандартным методом и выводим результат.

2. Наблюдения

• Требуется вывести не индексы и не количество перестановок, а именно сам массив после сортировки.
• Подходит обычная сортировка по возрастанию.
• Так как n может быть до 2 * 10^5, нужен достаточно быстрый алгоритм.
• Стандартная сортировка в C++ и Python работает за O(n log n), чего достаточно при таких ограничениях.
• Числа могут быть отрицательными, нулевыми и большими по модулю, но для стандартной сортировки это не проблема.

3. Алгоритм

1. Считать число n.
2. Считать массив из n целых чисел.
3. Отсортировать массив по возрастанию.
4. Вывести все элементы массива через пробел.

4. Почему это работает

После сортировки по возрастанию элементы массива располагаются так, что для любых соседних элементов выполняется условие: левый не больше правого.

Именно это и означает порядок по неубыванию, который требуется в задаче.

Так как сортировка переставляет элементы массива в нужный порядок и сохраняет все исходные значения, на выходе получается ровно тот набор чисел, который был во входных данных, но уже отсортированный.

5. Сложность

• Время: O(n log n) из-за сортировки.
• Память: O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

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