It is known that there are k fish species in the polar ocean, numbered from 1 to k. They are sorted by non-decreasing order of their weight, which is a positive number. Let the weight of the i-th type of fish be w_{i}, then 0 < w_1 ≤ w_2 ≤ ... ≤ w_{k} holds.

Polar bears Alice and Bob each have caught some fish, and they are guessing who has the larger sum of weight of the fish he/she's caught. Given the type of the fish they've caught, determine whether it is possible that the fish caught by Alice has a strictly larger total weight than Bob's. In other words, does there exist a sequence of weights w_{i} (not necessary integers), such that the fish caught by Alice has a strictly larger total weight?


-----Input-----

The first line contains three integers n, m, k (1 ≤ n, m ≤ 10^5, 1 ≤ k ≤ 10^9) — the number of fish caught by Alice and Bob respectively, and the number of fish species.

The second line contains n integers each from 1 to k, the list of fish type caught by Alice. The third line contains m integers each from 1 to k, the list of fish type caught by Bob.

Note that one may have caught more than one fish for a same species.


-----Output-----

Output "YES" (without quotes) if it is possible, and "NO" (without quotes) otherwise.


-----Examples-----
Input
3 3 3
2 2 2
1 1 3

Output
YES

Input
4 7 9
5 2 7 3
3 5 2 7 3 8 7

Output
NO



-----Note-----

In the first sample, if w_1 = 1, w_2 = 2, w_3 = 2.5,  then Alice has a total of 2 + 2 + 2 = 6 weight units, while Bob only has 1 + 1 + 2.5 = 4.5.

In the second sample, the fish that Alice caught is a subset of Bob's. Therefore, the total weight of Bob’s fish is always not less than the total weight of Alice’s fish.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
import copy
import itertools
import string
import sys

def powmod(x, p, m):
	if p <= 0:
		return 1
	if p <= 1:
		return x % m
	return powmod(x * x % m, p // 2, m) * (x % m) ** (p % 2) % m

def to_basex(num, x):
	while num > 0:
		yield (num % x)
		num //= x

def from_basex(it, x):
	ret = 0
	p = 1
	for d in it:
		ret += d * p
		p *= x
	return ret

def core():
	_ = input()
	a = [int(x) for x in input().split()]
	r = [int(x) for x in input().split()]
	a.sort()
	r.sort()
	while len(a) > 0 and len(r) > 0 and (r[-1] >= a[-1]):
		a.pop()
		r.pop()
	ans = 'YES' if len(a) > 0 else 'NO'
	print(ans)
core()


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort(key=lambda x: -x)
b.sort(key=lambda x: -x)
t = False
n1 = min(m, n)
if n > m:
	t = True
else:
	for i in range(n1):
		if a[i] > b[i]:
			t = True
if t:
	print('YES')
else:
	print('NO')


from collections import defaultdict
(n, k, p) = (0, 0, defaultdict(int))
input()
for i in map(int, input().split()):
	p[i] += 1
for i in map(int, input().split()):
	p[i] -= 1
r = sorted(list(p.keys()), reverse=True)
for i in r:
	n += p[i]
	if n > 0:
		break
print('YES' if n > 0 else 'NO')


(a, b, _c) = list(map(int, input().split()))
af = list(map(int, input().split()))
bf = list(map(int, input().split()))
af.sort(reverse=True)
bf.sort(reverse=True)
aflen = len(af)
bflen = len(bf)
i = 0
j = 0
cnt = 0
while i < aflen and j < bflen:
	if af[i] > bf[j]:
		cnt += 1
		i += 1
	elif af[i] < bf[j]:
		cnt -= 1
		j += 1
	else:
		i += 1
		j += 1
	if cnt > 0:
		print('YES')
		break
else:
	cnt += aflen - i
	if cnt > 0:
		print('YES')
	else:
		print('NO')


rd = lambda : list(map(int, input().split()))
rd()
a = sorted(rd(), reverse=True)
b = sorted(rd(), reverse=True)
if len(a) > len(b):
	print('YES')
	return
for i in range(len(a)):
	if a[i] > b[i]:
		print('YES')
		return
print('NO')


(n, m, k) = list(map(int, input().split()))
Alice = list(map(int, input().split()))
Bob = list(map(int, input().split()))
SA = {}
SB = {}
for item in Alice:
	if item in SA:
		SA[item] += 1
		continue
	SA[item] = 1
	SB[item] = 0
for item in Bob:
	if item in SB:
		SB[item] += 1
		continue
	SB[item] = 1
	SA[item] = 0
x = sorted(list(set(Alice + Bob)), reverse=True)
n = len(x)
done = False
i = 0
needed = 0
while i < n:
	if SA[x[i]] - SB[x[i]] > needed:
		print('YES')
		done = True
		break
	needed += SB[x[i]] - SA[x[i]]
	i += 1
if not done:
	print('NO')


(n, m, k) = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
cou = ind = 0
l = min(m, n)
aa = max(b)
for i in range(l):
	if a[i] > b[i]:
		cou += 1
		ind = max(ind, a[i])
if m >= n and cou > 0:
	print('YES')
elif m < n:
	print('YES')
else:
	print('NO')


(n, m, k) = [int(x) for x in input().split()]
alice = [int(x) for x in input().split()]
bob = [int(x) for x in input().split()]
alice.sort()
bob.sort()
balance = 0
i = n - 1
j = m - 1
while i >= 0 and j >= 0:
	if alice[i] > bob[j]:
		balance += 1
		i -= 1
	elif alice[i] < bob[j]:
		balance -= 1
		j -= 1
	else:
		i -= 1
		j -= 1
	if balance > 0:
		break
if i + 1 + balance > 0:
	print('YES')
else:
	print('NO')


(n, m, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
ans = 'NO'
if n > m:
	ans = 'YES'
else:
	for i in range(n):
		if a[i] > b[i]:
			ans = 'YES'
print(ans)


import sys
from math import gcd, sqrt, ceil
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
from itertools import permutations
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')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = set()
	sa.add(n)
	while n % 2 == 0:
		sa.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.add(i)
			n = n // i
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def check_prim(n):
	if n < 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
(n, m, k) = map(int, input().split())
hash1 = defaultdict(int)
hash2 = defaultdict(int)
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
w = defaultdict(lambda : 1)
ha = set()
for i in l1:
	hash1[i] += 1
	ha.add(i)
for i in l2:
	hash2[i] += 1
	ha.add(i)
(w1, w2) = (0, 0)
ha = list(ha)
ha.sort()
prev = 1
for i in ha:
	(z1, z2) = (hash1[i], hash2[i])
	if hash2[i] >= hash1[i]:
		w[i] = prev
	elif w1 >= w2:
		w[i] = prev + 1
	else:
		w[i] = w2 - w1 + 2
	w1 += hash1[i] * w[i]
	w2 += hash2[i] * w[i]
	prev = w[i]
if w1 > w2:
	print('YES')
else:
	print('NO')


import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
for i in range(n):
	bb = b[i] if i < m else 0
	if a[i] > bb:
		print('YES')
		exit()
print('NO')


(n, m, k) = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
for i in range(n):
	if a[-i - 1] > int(b[-i - 1] if i < m else 0):
		print('YES')
		break
else:
	print('NO')


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	(n, m, k) = lst()
	f = 0
	a = sorted(lst(), reverse=1)
	b = sorted(lst(), reverse=1)
	p = p1 = 0
	while p < n and p1 < m:
		if a[p] > b[p1]:
			f = 1
			break
		p += 1
		p1 += 1
	if p < n and p1 >= m:
		f = 1
	print('YES' if f else 'NO')