Студенты получили новое задание по криптографии.
Преподаватель дал им массив целых неотрицательных чисел $$$a$$$ длины $$$n$$$. Известно, что массив был зашифрован: каждый элемент массива мог быть уменьшен не более чем на $$$r$$$ или увеличен не более чем на $$$l$$$. Иными словами, если в зашифрованном массиве элемент равен $$$a_i$$$, то изначально он мог быть любым целым неотрицательным числом от $$$a_i - l$$$ до $$$a_i + r$$$ включительно. Также известно, что все числа в массиве до того, как его зашифровали, также были неотрицательными.
Студентам был задан вопрос — мог ли массив быть отсортированным по неубыванию до того, как его зашифровали? Помогите студентам ответить на этот непростой вопрос.
В первой строке вводятся три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$, $$$0 \le l, r \le 10^{9}$$$) — длина массива и числа $$$l$$$, $$$r$$$.
Во второй строке вводится $$$n$$$ целых неотрицательных чисел $$$a_1, a_2...a_n$$$ ($$$0 \le a_i \le 10^{9}$$$) — зашифрованный массив.
В единственной строке выведите «YES» или «NO» (без кавычек) — ответ на поставленный вопрос.
Баллы за подгруппу начисляются в случае прохождения всех тестов подгруппы, а также всех тестов необходимых подгрупп.
| Подгруппа | Баллы | Дополнительные ограничения | Необходимые подгруппы |
| $$$0$$$ | $$$0$$$ | Тесты из условия | — |
| $$$1$$$ | $$$11$$$ | $$$ n = 2, l + r + 1 \le 50$$$ | — |
| $$$2$$$ | $$$12$$$ | $$$ n = 3, l + r + 1 \le 50$$$ | — |
| $$$3$$$ | $$$12$$$ | $$$ n \le 500, l + r + 1 \le 100$$$ | 0, 1, 2 |
| $$$4$$$ | $$$17$$$ | $$$ n \le 2000, l + r + 1 \le 2000$$$ | 0, 1, 2, 3 |
| $$$5$$$ | $$$15$$$ | $$$ l = 0$$$ | — |
| $$$6$$$ | $$$33$$$ | без дополнительных ограничений | 0 — 5 |
4 1 21 0 2 1
YES
3 2 25 0 5
NO
4 0 22 1 1 0
YES
В первом примере изначальный массив мог быть таким: [0, 2, 2, 3].
В третьем примере изначальный массив мог быть таким: [2, 2, 2, 2].
| Олимпиада 1С 2026, предметный тур |
|---|
| Закончено |
