During the "Russian Code Cup" programming competition, the testing system stores all sent solutions for each participant. We know that many participants use random numbers in their programs and are often sent several solutions with the same source code to check.

Each participant is identified by some unique positive integer k, and each sent solution A is characterized by two numbers: x — the number of different solutions that are sent before the first solution identical to A, and k — the number of the participant, who is the author of the solution. Consequently, all identical solutions have the same x.

It is known that the data in the testing system are stored in the chronological order, that is, if the testing system has a solution with number x (x > 0) of the participant with number k, then the testing system has a solution with number x - 1 of the same participant stored somewhere before.

During the competition the checking system crashed, but then the data of the submissions of all participants have been restored. Now the jury wants to verify that the recovered data is in chronological order. Help the jury to do so.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^5) — the number of solutions. Each of the following n lines contains two integers separated by space x and k (0 ≤ x ≤ 10^5; 1 ≤ k ≤ 10^5) — the number of previous unique solutions and the identifier of the participant.


-----Output-----

A single line of the output should contain «YES» if the data is in chronological order, and «NO» otherwise.


-----Examples-----
Input
2
0 1
1 1

Output
YES

Input
4
0 1
1 2
1 1
0 2

Output
NO

Input
4
0 1
1 1
0 1
0 2

Output
YES

Difficulty: MEDIUM
Tags: Implementation

Starter code:

Solutions:
n = int(input())
user = 100001 * [-1]
for i in range(n):
	(x, k) = map(int, input().split())
	if user[k] == x - 1:
		user[k] = x
	elif user[k] < x - 1:
		print('NO')
		exit()
print('YES')


def adds(s, x, k):
	if k in s.keys():
		xs = s[k]
		if x <= xs:
			return 0
		elif x - 1 == xs:
			s[k] = x
			return 0
		else:
			return 1
	elif x == 0:
		s[k] = 0
		return 0
	else:
		return 1

def corr(v):
	s = dict()
	for c in v:
		if adds(s, c[0], c[1]):
			return 0
	return 1
n = int(input())
v = []
for c in range(n):
	(x, k) = map(int, input().split(' '))
	v.append((x, k))
if corr(v):
	print('YES')
else:
	print('NO')


n = int(input())
participants = {}
order = True
while n:
	n -= 1
	(x, k) = map(int, input().split())
	if k in participants:
		if x in participants[k]:
			continue
		elif x - 1 in participants[k]:
			participants[k].add(x)
		else:
			order = False
			break
	else:
		if x != 0:
			order = False
			break
		tmp = set()
		tmp.add(x)
		participants[k] = tmp
if order:
	print('YES')
else:
	print('NO')


import sys
import math
n = int(sys.stdin.readline())
d = dict()
for i in range(n):
	(x, k) = [int(x) for x in sys.stdin.readline().split()]
	if k in d:
		t = d[k]
		if x not in t[1]:
			if x - 1 == t[0]:
				t[0] = x
				t[1].add(x)
			else:
				print('NO')
				return
	else:
		if x > 0:
			print('NO')
			return
		d[k] = [x, {x}]
print('YES')


c = [0] * 100001
for i in range(int(input())):
	(x, k) = map(int, input().split())
	if x == c[k]:
		c[k] += 1
	elif x > c[k]:
		print('NO')
		exit()
print('YES')


import sys
from array import array
f = sys.stdin
n = int(f.readline())
ans = 'YES'
submissions = [0] * n
i = 0
for line in f:
	arr = line.split(' ')
	x = int(arr[0])
	k = int(arr[1]) - 1
	while k < 0 or k >= len(submissions):
		submissions.extend([0] * len(submissions))
	if submissions[k] < x:
		ans = 'NO'
		break
	if submissions[k] == x:
		submissions[k] = submissions[k] + 1
	i = i + 1
	if i >= n:
		break
print(ans)


n = int(input())
m = []
d = dict()
for i in range(n):
	(x, k) = map(int, input().split())
	if k in d:
		r = d[k]
		if x > r + 1:
			print('NO')
			return
		d[k] = max(r, x)
	else:
		if x != 0:
			print('NO')
			return
		d[k] = x
print('YES')


d = [0] * 100001
for _ in range(int(input())):
	(v, k) = map(int, input().split())
	if v > d[k]:
		print('NO')
		exit()
	elif v == d[k]:
		d[k] += 1
print('YES')


import sys
from collections import defaultdict
n = int(sys.stdin.readline())
d = defaultdict(lambda : -1)
for i in range(0, n):
	(x, k) = map(int, sys.stdin.readline().split())
	z = d[k]
	if x == z + 1:
		d[k] = x
	elif x > z + 1:
		print('NO')
		sys.exit(0)
print('YES')


n = int(input())
r = ['NO', 'YES']
d = {}
for _ in range(n):
	(x, k) = list(map(int, input().split(' ')))
	a = d.get(k, -1)
	if a + 1 < x:
		print(r[0])
		return
	elif a + 1 == x:
		d[k] = x
print(r[1])


def solve():
	n = int(input())
	p = True
	d = []
	for _ in range(int(100000.0 + 1)):
		d.append(set())
	for _ in range(n):
		(x, k) = map(int, input().split())
		if x > 0 and x - 1 not in d[k]:
			p = False
		else:
			d[k].add(x)
	print('YES' if p else 'NO')
solve()


a = []
d = {}
flag = 0
for t in range(int(input())):
	(x, y) = map(int, input().split())
	if y in d.keys():
		if x == 0 and len(d[y]) == 0:
			d[y].append(x)
		if d[y][len(d[y]) - 1] + 1 == x:
			d[y].append(x)
		elif x <= d[y][len(d[y]) - 1]:
			continue
		else:
			flag = 1
			break
	else:
		d[y] = []
		if x != 0:
			flag = 1
			break
		else:
			d[y].append(0)
if flag == 0:
	print('YES')
else:
	print('NO')


def readln():
	return tuple(map(int, input().split()))
(n,) = readln()
max_pref = [-1] * 100001
flag = True
for _ in range(n):
	(x, k) = readln()
	flag &= max_pref[k] + 1 >= x
	max_pref[k] = max(max_pref[k], x)
print('YES' if flag else 'NO')


from collections import deque
for _ in range(1):
	n = int(input())
	visited = set()
	flag = 1
	for i in range(n):
		(x, k) = map(int, input().split())
		if x == 0:
			visited.add((x, k))
		elif (x - 1, k) in visited:
			visited.add((x, k))
		else:
			flag = 0
	if flag:
		print('YES')
	else:
		print('NO')


import sys
f = sys.stdin
n = int(f.readline().strip())
people = {}
res = 'YES'
for i in range(n):
	(x, k) = map(int, f.readline().strip().split())
	if k in people:
		if x == people[k] + 1:
			people[k] = x
		elif x <= people[k]:
			pass
		else:
			res = 'NO'
			break
	elif x == 0:
		people[k] = x
	else:
		res = 'NO'
		break
print(res)


p = {}
for i in range(int(input())):
	(x, k) = map(int, input().split())
	if k in p:
		if x == p[k] + 1:
			p[k] = x
		elif x > p[k]:
			print('NO')
			return
	elif x:
		print('NO')
		return
	else:
		p[k] = 0
print('YES')


sol = int(input())
list1 = []
for i in range(10 ** 5 + 1):
	list1.append([])
for i in range(sol):
	(a, b) = input().split()
	b = int(b)
	list1[b].append(a)
i = 0
v = True
while i < 10 ** 5 + 1 and v:
	j = 0
	z = -1
	while j < len(list1[i]) and v:
		if int(list1[i][j]) - z == 1:
			z = int(list1[i][j])
		elif int(list1[i][j]) - z > 1:
			v = False
		j += 1
	i += 1
if v == True:
	print('YES')
else:
	print('NO')


n = int(input())
ks = []
for i in range(100001):
	ks.append(-1)
v = True
for i in range(n):
	(x, k) = map(int, input().split())
	if v:
		if x > ks[k] + 1:
			v = False
		elif x > ks[k]:
			ks[k] = x
if v:
	print('YES')
else:
	print('NO')


n = int(input())
tasks = {}
fail = False
for i in range(n):
	(x, k) = list(map(int, input().split()))
	if k not in tasks:
		if x == 0:
			tasks[k] = {x}
		else:
			fail = True
			break
	elif x == 0:
		if x in tasks[k]:
			tasks[k].add(x)
		else:
			fail = True
			break
	elif x > 0:
		if x - 1 in tasks[k]:
			tasks[k].add(x)
		else:
			fail = True
			break
	else:
		fail = True
		break
if fail:
	print('NO')
else:
	print('YES')


recovery = [-1] * 100001
solution = int(input())
for s in range(solution):
	(sol, user) = map(int, input().split())
	if recovery[user] == sol - 1:
		recovery[user] = sol
	elif recovery[user] >= sol:
		continue
	else:
		print('NO')
		return
print('YES')


n = int(input())
p = 0
a = []
for _ in range(n):
	(x, k) = list(map(int, input().split()))
	while k > len(a):
		a.append(-1)
	k = k - 1
	if a[k] < x - 1:
		print('NO')
		exit()
	else:
		a[k] = max(x, a[k])
print('YES')


n = int(input())
d = {}
for i in range(n):
	p = list(map(int, input().split()))
	if p[0] == 0:
		d[p[1]] = d.get(p[1], 0)
	else:
		if p[0] - d.get(p[1], -1) > 1:
			print('NO')
			exit()
		d[p[1]] = max(d[p[1]], p[0])
print('YES')


n = int(input())
a = [-1] * 100001
p = 0
for i in range(n):
	(x, k) = map(int, input().split())
	if a[k] < x - 1:
		p = 1
	else:
		a[k] = max(a[k], x)
if p:
	print('NO')
else:
	print('YES')


import sys
n = int(input())
c = [-1] * (10 ** 5 + 1)
for i in range(n):
	(x, k) = list(map(int, input().split()))
	if c[k] < x - 1:
		print('NO')
		return
	else:
		c[k] = max(c[k], x)
print('YES')


data = {}
for _ in range(int(input())):
	(x, k) = map(int, input().split())
	if k in data:
		data[k].append(x)
	else:
		data[k] = [x]
flag = True
for counts in data.values():
	allowed = 0
	for count in counts:
		if count > allowed:
			flag = False
			break
		if count == allowed:
			allowed += 1
	if not flag:
		break
print(['NO', 'YES'][flag])


n = int(input())
res = 'YES'
uch = {}
zap = [0, 0]
for i in range(0, n):
	zap = list(map(int, input().split()))
	if zap[1] in uch:
		if zap[0] == uch[zap[1]] + 1:
			uch[zap[1]] = zap[0]
		elif zap[0] > uch[zap[1]] + 1:
			res = 'NO'
	elif zap[0] == 0:
		uch[zap[1]] = zap[0]
	else:
		res = 'NO'
print(res)


import sys

def main():
	f = sys.stdin
	n = int(f.readline())
	count = dict()
	for _ in range(n):
		(x, k) = map(int, f.readline().split())
		if k not in count:
			count[k] = -1
		if count[k] < x - 1:
			print('NO')
			return
		count[k] = max(count[k], x)
	print('YES')
main()


n = int(input())
from collections import defaultdict
a = defaultdict(lambda : {-1})
for i in range(n):
	(x, k) = map(int, input().split())
	p = a[k]
	if x - 1 not in p:
		print('NO')
		break
	else:
		a[k].add(x)
else:
	print('YES')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
n = int(input())
f = 0
ls = [-1] * (10 ** 5 + 4)
for i in range(n):
	(n, k) = map(int, input().split())
	if n > ls[k] + 1:
		f = 1
	ls[k] = max(ls[k], n)
if f == 1:
	print('NO')
else:
	print('YES')


all = {}
n = int(input())
ans = True
for i in range(n):
	x_k = input().split()
	x = int(x_k[0])
	k = int(x_k[1])
	if k not in all:
		all[k] = -1
	if all[k] >= x:
		pass
	elif all[k] + 1 != x:
		ans = False
		break
	else:
		all[k] = x
if ans:
	print('YES')
else:
	print('NO')