Start: Apr, 14, 2021 19:45:00
2021春ACM通识课考试(第一场)(补题)
End: Dec, 31, 2021 23:00:00
Time elapsed:
Time remaining:

魔女日记 2866

Time Limit:  2 s      Memory Limit:   256 MB
Submission:179     AC:23     Score:0

Description

      众所周知,灰之魔女伊蕾娜年纪轻轻便成为最高阶魔法师魔女的少女。对幼时阅读的《妮可冒险记》怀抱憧憬,因而成为旅人。在她旅行的途中,他经过了很多很多的国家,并一一记录了下来。她对《妮可冒险记》中不同的故事有不同的有趣程度,同样她对自己的日记中记录下来的不同的国家也有不同程度。为了更好地向她的老师芙兰介绍他的旅途,所以她想用日记的有趣程度从小到大来给自己的日记重新编排一下顺序。那个美丽又聪明的魔女,没错就是伊蕾娜很快的就想到可以通过冒泡排序的方法来排序,就是每一个比较相邻的两篇日记的大小,然后判断是否需要交换两篇日记的顺序来完成排序。不过她还遇到了一个问题。

一篇日记有两个参数ac。分别代表着日记的有趣程度和这篇日记所属于的故事。由于不同的几篇日记可能记录的是同一个故事的不同日期,所以不能交换它们的顺序(否则故事就会不连贯)。即如果在冒泡排序中相邻的两篇日记属于相同的故事时,那么两篇日记被禁止交换交换。

现在需要你帮她想想办法,看看她的日记能不能被完美的从小到大的排序。

Input

第一行包含一个整数n( 1 ≤ n ≤ 200000) 代表着日记的总篇数。

接下来有n行,每一行包含aici (-1e9≤ ai ≤ 1e9,1 ≤ ci ≤ 200000),即第 i 篇日记的有趣程度和所属的故事。

Output

输出“YES”或者“NO”,分别对应能否被完美的从小到大的排序来决定。

Samples

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

Hint

在第一个测试中,以下操作序列对数组进行排序:

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)以对日记进行排序,这种交换是被禁止的,所以不能交换成功(答案输出“NO”)。