406844: GYM102569 I Sorting Colored Array

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Sorting Colored Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

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

ExamplesInput
6
1 2
-1 3
-3 1
3 2
0 1
2 3
Output
YES
Input
6
1 2
-1 1
-3 1
3 2
0 3
2 3
Output
NO
Note

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.

加入题单

上一题 下一题 算法标签: