← 返回题目列表

Codeforces · 417/B

B. 崩溃

中文机器翻译题面 查看原题

“俄罗斯代码杯”编程竞赛期间,测试系统存储每位参赛者所有发送的解决方案。我们知道许多参与者在他们的程序中使用随机数,并且经常会收到多个具有相同源代码的解决方案进行检查。

每个参与者都由某个唯一的正整数 k 标识,每个发送的解决方案 A 由两个数字来表征:x - 在第一个与 A 相同的解决方案之前发送的不同解决方案的数量,k - 参与者的编号,即该解决方案的作者。因此,所有相同的解都具有相同的 x。

已知测试系统中的数据是按时间顺序存储的,即如果测试系统中存在第k个参与者的编号为x(x > 0)的解,则测试系统之前在某处存储有同一参与者的编号为x - 1的解。

比赛期间检查系统崩溃,但随后所有参赛者提交的作品数据均已恢复。现在陪审团想要验证恢复的数据是否按时间顺序排列。帮助陪审团这样做。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 105) - 解的数量。以下 n 行中的每一行都包含两个由空格 x 和 k 分隔的整数(0 ≤ x ≤ 105;1 ≤ k ≤ 105)——之前唯一解决方案的数量和参与者的标识符。

输出

如果数据按时间顺序排列,则输出的单行应包含“YES”,否则应包含“NO”。

示例

输入 #1

2
0 1
1 1

输出 #1

YES

输入 #2

4
0 1
1 2
1 1
0 2

输出 #2

NO

输入 #3

4
0 1
1 1
0 1
0 2

输出 #3

YES