1. Идея

Нужно проверить, отсортирован ли массив по неубыванию.

Неубывание означает, что для каждой пары соседних элементов должно выполняться условие: следующий элемент не меньше предыдущего. То есть не должно быть ни одной позиции, где a[i] < a[i - 1].

Поэтому достаточно один раз пройти по массиву слева направо и проверить все соседние пары.

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

• Если массив состоит из одного элемента, то он всегда отсортирован.
• Если хотя бы в одном месте встретилось a[i] < a[i - 1], ответ сразу NO.
• Если такой пары нет, значит для всех соседних элементов выполнено a[i] >= a[i - 1], а значит массив отсортирован по неубыванию.

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

3. Алгоритм

1. Считать n.
2. Считать массив a из n чисел.
3. Для всех индексов от 1 до n - 1:
   • если a[i] < a[i - 1], вывести NO и завершить программу.
4. Если цикл завершился без нарушений, вывести YES.

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

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

Это определение напрямую сводится к проверке всех соседних пар:

• если для каждой пары соседей выполнено a[i] >= a[i - 1], то массив неубывающий;
• если найдётся хотя бы одна пара, где a[i] < a[i - 1], то порядок нарушен, и массив уже не является неубывающим.

Значит, описанный алгоритм проверяет ровно то условие, которое требуется в задаче, и потому всегда даёт правильный ответ.

5. Сложность

• Время работы: O(n), потому что массив просматривается один раз.
• Дополнительная память: O(n), так как в эталонном решении массив считывается целиком.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

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

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

    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

7. Код на Python 3

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

ok = True
for i in range(1, n):
    if a[i] < a[i - 1]:
        ok = False
        break

print("YES" if ok else "NO")