Чтобы отблагодарить Яна, Мэри подарила ему массив \(a\) длины \(n\). Чтобы выглядеть умным, он хочет отсортировать массив в порядке неубывания, выполнив следующее конечное число раз: он выбирает два соседних элемента \(a_i\) и \(a_{i+1}\) (\(1\le i\le n-1\)), и увеличивает оба их на \(1\) или уменьшает оба их на \(1\). Заметим, что элементы массива могут стать отрицательными.
Как умный человек, вы заметили, что, существуют массивы, которые Ян не сможет отсортировать в порядке неубывания! Поэтому вы решили написать программу, чтобы определить, можно ли сделать массив отсортированным в неубывающем порядке.
Выходные данные
Для каждого набора входных данных выведите «YES», если существует последовательность операций, которая сделает массив отсортированным в порядке неубывания, иначе выведите «NO».
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных мы можем увеличить \(a_2\) и \(a_3\) на \(1\). Теперь массив стал \([1, 4, 3]\).
Затем мы можем уменьшить \(a_1\) и \(a_2\) на \(1\). Теперь массив стал \([0, 3, 3]\), который отсортирован в порядке неубывания. Поэтому ответ «YES».
Во втором наборе входных данных без разницы как Ян будет применять операции, \(a_1\) всегда останется больше \(a_2\). Поэтому ответ «NO», и Ян не сможет показаться умным.
В третьем наборе входных данных массив уже отсортирован в порядке неубывания, поэтому Яну не нужно ничего делать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 3 2
2
2 1
4
1 3 5 7
4
2 1 4 3
5
5 4 3 2 1
|
YES
NO
YES
NO
YES
|