406844: GYM102569 I Sorting Colored Array

You are given the array of $$$n$$$ integers. Each number in the array is colored. In one operation you can swap two adjacent differently colored elements. Is it possible to sort the array with some number of such operations?

The first line contains the integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the size of the array.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$, $$$c_i$$$ ($$$-10^9 \le a_i \le 10^9, 1 \le c_i \le 200000$$$) — the value of the $$$i$$$-th element of the array and its color.

Output "YES" or "NO", depending on is it possible to sort the array using the given operation or not.

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

In the first test the following sequence of operations sorts the array:

1) swap (1, 2) and (-1, 3)

2) swap (1, 2) and (-3, 1)

3) swap (-1, 3) and (-3, 1)

4) swap (3, 2) and (0, 1)

5) swap (1, 2) and (0, 1)

6) swap (3, 2) and (2, 3)

The resulting array will be:

-3 1

-1 3

0 1

1 2

2 3

3 2

In the second test the elements (-1, 1) and (-3, 1) must be swapped to sort the array, but such swap is prohibited.