I. Sorting Colored Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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.

Examples
Input
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.