Read problem statements in [Mandarin], [Bengali], and [Russian] as well.

Chef is a wanted criminal, and N police officers are up for catching him. The officers want to catch Chef no matter the cost, and Chef also wants to eliminate as many officers as possible (preferably everyone) before getting caught (or before running away after eliminating everyone). Neither the officers nor Chef will run away before accomplishing their goals.

Chef and the officers are on a one-dimensional grid with coordinates ranging from -10^{10} to 10^{10}. Chef is initially standing at coordinate C, and the i-th officer is initially at coordinate P_{i}. The officers and Chef then take turns to move, with the officer team moving first. 

During their turn, officers will have to move to an adjacent unoccupied cell one by one, in any order they want. Every officer will have to move. At every moment of time, no two officers can be in the same cell, and also no officer can be in the same cell as Chef. If the officer is unable to move to an adjacent unoccupied cell, he is eliminated (and the cell he was in becomes unoccupied). Note that the officer team will try to move to eliminate as few officers as possible. For example, with P = [2, 3, 4] and C = 6, then the next positions of the officers can be [1, 2, 3], [1, 2, 5], [1, 4, 5], or [3, 4, 5]. However, with P = [2, 3, 4] and C = 5, the only possible set of the next positions of the officers is [1, 2, 3].

After the officer team's turn, Chef also moves to an adjacent unoccupied cell, or gets caught if he cannot find any adjacent unoccupied cell. The process then repeats until either Chef is caught, or all officers are eliminated and Chef runs away.

You need to find out the maximum number of officers that can be eliminated by Chef, and if Chef can run away or not.

As a reminder, two cells with coordinates X and Y are *adjacent* if and only if |X - Y| = 1.

------ Input Format ------ 

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N - the number of officers.
- The second line of each test case contains a single integer C - the initial coordinate of Chef.
- The third line of each test case contains N integers P_{1}, P_{2}, \dots, P_{N} - the initial coordinates of the officers.

------ Output Format ------ 

For each test case, output on a single line two space-separated integers: the first integer is the maximum number of officers that can be eliminated by Chef, and the second integer is 1 if Chef runs away or -1 if Chef will be caught.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ C ≤ 10^{9}$
$1 ≤ P_{i} ≤ 10^{9}$
- All the coordinates are unique. That means $P_{i} \ne C$ for all $1 ≤i ≤N$, and $P_{i} \ne P_{j}$ for all $1 ≤i < j ≤N$

----- Sample Input 1 ------ 
2
2
2
1 4
1
2
1

----- Sample Output 1 ------ 
1 -1
1 1

----- explanation 1 ------ 
- Test case $1$: Chef chooses to always move to the left (i.e. to the smaller coordinate); this forces the officer at coordinate $1$ to always move to the left, and eventually being cornered and eliminated. However, the officer at coordinate $4$ cannot be eliminated, and hence Chef will be caught at the end.
- Test case $2$: Similarly, Chef chooses to always move to the left, and eventually eliminating the only officer, thus running away at the end.

Difficulty: VERY_HARD
Tags: Sorting

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Sorting

Starter code:

Solutions:
def location(c, p, l, r):
	mid = (l + r) // 2
	if p[mid] > c and p[mid - 1] < c:
		return mid - 1
	elif p[mid - 1] > c:
		return location(c, p, l, mid)
	elif p[mid] < c:
		return location(c, p, mid, r)
for _ in range(int(input())):
	n = int(input())
	c = int(input())
	p = list(map(int, input().split()))
	p = sorted(p)
	if n == 1:
		if p[0] > c:
			l = -1
		else:
			l = 0
	elif n == 2:
		if p[0] > c:
			l = -1
		elif p[0] < c and p[1] > c:
			l = 0
		else:
			l = 1
	elif p[0] > c:
		l = -1
	elif p[-1] < c:
		l = n - 1
	else:
		l = location(c, p, 0, n)
	ans = 0
	xd = 1
	if l == -1:
		for i in range(n):
			if (c + p[i]) % 2 == 1:
				ans += 1
			else:
				xd = -1
				break
	elif l == n - 1:
		for i in range(-1, -n - 1, -1):
			if (c + p[i]) % 2 == 1:
				ans += 1
			else:
				xd = -1
				break
	else:
		a = b = 0
		for i in range(l, -1, -1):
			if (c + p[i]) % 2 == 1:
				a += 1
			else:
				xd = -1
				break
		for i in range(l + 1, n + 1):
			if (c + p[i]) % 2 == 1:
				b += 1
			else:
				xd = -1
				break
		ans = a + b
	print(ans, xd)


from sys import stdin
input = stdin.readline

def answer():
	j = n
	for i in range(n):
		if c < a[i]:
			j = i
			break
	(ans, i) = (0, j - 1)
	while i >= 0 and a[i] & 1 != c & 1:
		ans += 1
		i -= 1
	while j < n and a[j] & 1 != c & 1:
		ans += 1
		j += 1
	if ans == n:
		return [ans, 1]
	return [ans, -1]
for T in range(int(input())):
	n = int(input())
	c = int(input())
	a = sorted(list(map(int, input().split())))
	print(*answer())


t = int(input())
for i in range(t):
	n = int(input())
	c = int(input())
	a = sorted(list(map(int, input().split())) + [c])
	p = a.index(c)
	ans = 0
	for j in range(p + 1, len(a)):
		if a[j] % 2 == c % 2:
			break
		ans += 1
	for k in reversed(range(p)):
		if a[k] % 2 == c % 2:
			break
		ans += 1
	print(ans, 1 if ans == n else -1)


for _ in range(int(input())):
	n = int(input())
	c = int(input())
	a = sorted(list(map(int, input().split())) + [c])
	pos = a.index(c)
	ans = 0
	for i in range(pos + 1, len(a)):
		if a[i] % 2 == c % 2:
			break
		ans += 1
	for i in reversed(range(pos)):
		if a[i] % 2 == c % 2:
			break
		ans += 1
	print(ans, 1 if ans == n else -1)


for _ in range(int(input())):
	n = int(input())
	c = int(input())
	a = list(map(int, input().split()))
	a.append(c)
	a.sort()
	pos = a.index(c)
	ans = 0
	for i in range(pos + 1, len(a)):
		if a[i] % 2 == c % 2:
			break
		ans += 1
	for i in range(pos - 1, -1, -1):
		if a[i] % 2 == c % 2:
			break
		ans += 1
	print(ans, end=' ')
	if ans == n:
		print(1)
	else:
		print(-1)


import bisect
T = int(input())
for _ in range(T):
	N = int(input())
	C = int(input())
	P = list(map(int, input().split()))
	P.sort()
	index = bisect.bisect(P, C)
	c = 0
	l = index - 1
	r = index
	while l >= 0:
		if P[l] & 1 != C & 1:
			c += 1
		else:
			break
		l -= 1
	while r < N:
		if P[r] & 1 != C & 1:
			c += 1
		else:
			break
		r += 1
	print(c, end=' ')
	print(1 if c == N else -1)


from collections import Counter
from sys import stdin, stdout
import bisect
for _ in range(int(input())):
	n = int(input())
	c = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ind = bisect.bisect(a, c)
	bisect.insort(a, c)
	z = 0
	p = 0
	for i in range(ind + 1, n + 1):
		if (a[i] - a[ind]) % 2 != 0:
			p += 1
		else:
			z = 1
			break
	for i in range(ind):
		if (a[ind] - a[ind - 1 - i]) % 2 != 0:
			p += 1
		else:
			z = 1
			break
	if z == 1:
		print(p, -1)
	else:
		print(p, 1)


import sys
readline = sys.stdin.readline
T = int(readline())
for t in range(T):
	ans0 = 0
	ans1 = 1
	N = int(readline())
	C = int(readline())
	P = sorted(list(map(int, readline().split())))
	b = 0
	while b != N and P[b] < C:
		b += 1
	(b0, b1) = (b, b)
	while b0 and P[b0 - 1] % 2 != C % 2:
		b0 -= 1
	while b1 != N and P[b1] % 2 != C % 2:
		b1 += 1
	ans0 = b1 - b0
	ans1 = 1 if (b0, b1) == (0, N) else -1
	print(ans0, ans1)


for tcase in range(int(input())):
	n = int(input())
	c = int(input())
	p = list(map(int, input().split()))
	p.sort()
	i = 0
	while i < n and p[i] < c:
		i += 1
	(elim, runs_away) = (0, 1)
	j = i - 1
	while j >= 0 and (c - p[j]) % 2 == 1:
		j -= 1
		elim += 1
	if j >= 0:
		runs_away = -1
	j = i
	while j < n and (p[j] - c) % 2 == 1:
		j += 1
		elim += 1
	if j < n:
		runs_away = -1
	print(elim, runs_away)


import bisect
for _ in range(int(input())):
	N = int(input())
	C = int(input())
	P = list(map(int, input().split()))
	P.sort()
	b = bisect.bisect(P, C)
	(i, j) = (b - 1, b)
	e = 0
	while i >= 0 and P[i] - C & 1:
		i -= 1
		e += 1
	while j < N and P[j] - C & 1:
		j += 1
		e += 1
	print('{} {}'.format(e, 1 if e == N else -1))