Есть массив из $$$n$$$ целых чисел. Каждое число в массиве покрашено в какой-то цвет. За одну операцию можно поменять местами два соседних числа, покрашенные в разные цвета. Можно ли с помощью некоторого количества таких операций отсортировать массив?
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 200000$$$) — размер массива.
В каждой из следующих $$$n$$$ строк дано два числа $$$a_i$$$, $$$c_i$$$ ($$$-10^9 \le a_i \le 10^9, 1 \le c_i \le 200000$$$) — значение $$$i$$$-го элемента массива и его цвет.
Выведите «YES» или «NO», в зависимости от того, можно ли отсортировать массив с помощью данной операции или нет.
6 1 2 -1 3 -3 1 3 2 0 1 2 3
YES
6 1 2 -1 1 -3 1 3 2 0 3 2 3
NO
В первом тесте одним из корректных наборов операций обмена является следующий:
1) (1, 2) с (-1, 3)
2) (1, 2) с (-3, 1)
3) (-1, 3) с (-3, 1)
4) (3, 2) с (0, 1)
5) (1, 2) с (0, 1)
6) (3, 2) с (2, 3)
В итоге получится следующий массив:
-3 1
-1 3
0 1
1 2
2 3
3 2
Во втором тесте для сортировки массива необходимо обменять местами элементы (-1, 1) и (-3, 1), что нельзя сделать по условию.
Название |
---|