Chef initially had two non-empty arrays A and B, where both arrays contain distinct elements. Moreover, there is no common element in the arrays A and B.

Chef forms another array C from the arrays A and B using the following process :
Let X denote the leftmost element of array A and Y denote the leftmost element of array B.
If Y is smaller than X, delete Y from B and append it to the end of C.
If X is smaller than Y, delete X from A and append it to the end of C.
If either array A or B becomes empty, append all the remaining elements of the other array to the end of C.

Chef forgot the arrays A and B but remembers the array C. Find any two valid non-empty arrays A and B that will yield the given array C. If it is not possible, print -1.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a space-separated integer N  — the number of elements in array C.
- The next line contains N space-separated integers denoting the elements of the array C.

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

For each test case, if a solutions exists, print any two valid arrays A and B along with their lengths respectively . For example, if A= [1,7] and B =[4,10,2], then print it as :

2 
1 7
3
4 10 2

Else, if answer doesn't exist, print -1 in a single line.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$-10^{5} ≤ C_{i}≤  10^{5}$
- The sum of $N$ over all test cases won't exceed $10^{6}$.

----- Sample Input 1 ------ 
2
6
7 6 3 8 2 9
2
2 1

----- Sample Output 1 ------ 
3
7 6 3
3
8 2 9
-1

----- explanation 1 ------ 
Test case $1$: We have $A = [7,6,3]$ and $B = [8,2,9]$. 
- Move $1$: $X = 7$ and $Y = 8$. Since $X< Y$, we delete $X$ and append it to $C$. Thus, $A = [6, 3], B = [8, 2, 9],$ and $C = [7]$.
- Move $2$: $X = 6$ and $Y = 8$. Since $X< Y$, we delete $X$ and append it to $C$. Thus, $A = [3], B = [8, 2, 9],$ and $C = [7, 6]$.
- Move $3$: $X = 3$ and $Y = 8$. Since $X< Y$, we delete $X$ and append it to $C$. Thus, $A = [], B = [8, 2, 9],$ and $C = [7, 6, 3]$.
- Now, since $A$ is empty, append all elements of $B$ to $C$. Thus, $C = [7, 6, 3, 8, 2, 9]$.

Test case $2$: It can be shown that there exist no valid non-empty arrays $A$ and $B$.

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = []
	b = []
	if max(arr) == arr[0]:
		print(-1)
	else:
		ma = arr[0]
		n1 = -1
		for i in range(len(arr)):
			if arr[i] > ma:
				n1 = i
				break
		a = arr[:n1]
		b = arr[n1:]
		print(len(a))
		for i in a:
			print(i, end=' ')
		print()
		print(len(b))
		for i in b:
			print(i, end=' ')
		print()


T = int(input())
for _ in range(T):
	n = int(input())
	C = list(map(int, input().split()))
	A = []
	B = []
	X = C[0]
	A.append(X)
	for i in range(1, len(C)):
		if X > C[i]:
			A.append(C[i])
		else:
			B = C[i:len(C)]
			break
	if len(A) == 0 or len(B) == 0:
		print(-1)
	else:
		print(len(A))
		for i in A:
			print(i, end=' ')
		print('')
		print(len(B))
		for i in B:
			print(i, end=' ')
		print('')


t = int(input())
while t:
	n = int(input())
	l = []
	l = list(map(int, input().split()))
	a = []
	b = l
	a.append(b[0])
	b.pop(0)
	for i in range(0, n - 1):
		if b[0] < a[0]:
			a.append(b[0])
			b.pop(0)
		else:
			break
	if a == [] or b == []:
		print('-1')
	else:
		print(len(a))
		for i in a:
			(print(i, end=' '),)
		print('')
		print(len(b))
		for i in b:
			(print(i, end=' '),)
		print('')
	t = t - 1


t = int(input())
for _ in range(t):
	c = input()
	c = input()
	c = c.split()
	k = -1
	c[0] = int(c[0])
	max_ = c[0]
	for i in range(1, len(c)):
		c[i] = int(c[i])
		if c[i] > max_:
			k = i
			break
	if i == len(c):
		print(-1)
	elif k == -1:
		print(-1)
	else:
		print(k)
		t = ''
		for i in range(0, k):
			t = t + str(c[i]) + ' '
		print(t)
		t = ''
		print(len(c) - k)
		for i in range(k, len(c)):
			t = t + str(c[i]) + ' '
		print(t)


T = int(input())
while T > 0:
	n = int(input())
	data = list(map(int, input().split(' ')))
	for x in data:
		if data[0] < x:
			ind = data.index(x)
			break
	else:
		print('-1')
		T -= 1
		continue
	A = data[0:ind]
	B = data[ind:]
	print(len(A))
	print(' '.join(map(str, A)))
	print(len(B))
	print(' '.join(map(str, B)))
	T -= 1


def solve():
	n = int(input())
	list_c = [int(i) for i in input().split()]
	(arrayA, arrayB) = ([], [])
	maxElement = list_c[0]
	flag = 1
	for i in list_c:
		if i <= maxElement and flag == 1:
			arrayA.append(i)
		else:
			flag = 0
			arrayB.append(i)
	if len(arrayA) == n:
		print(-1)
		return
	print(len(arrayA))
	for i in arrayA:
		print(i, end=' ')
	print()
	print(len(arrayB))
	for i in arrayB:
		print(i, end=' ')
	print()
T = int(input())
while T > 0:
	T -= 1
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	index = -1
	for i in range(n):
		if l[i] > l[0]:
			index = i
			break
	if index != -1:
		a = l[:index]
		b = l[index:]
		print(len(a))
		for i in a:
			print(i, end=' ')
		print()
		print(len(b))
		for i in b:
			print(i, end=' ')
		print()
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ind = -1
	for i in range(n):
		if l[i] > l[0]:
			ind = i
			break
	if ind != -1:
		l1 = l[:ind]
		l2 = l[ind:]
		print(len(l1))
		for i in l1:
			print(i, end=' ')
		print()
		print(len(l2))
		for i in l2:
			print(i, end=' ')
		print()
	else:
		print('-1')


test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	c = list(map(int, input().split()))
	tem = c[0]
	i = 1
	while i < n and tem > c[i]:
		i = i + 1
	if i == n:
		print('-1')
	else:
		print(i)
		for j in range(0, i):
			print(c[j], end=' ')
		print()
		print(n - i)
		for j in range(i, n):
			print(c[j], end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	first = arr[0]
	index = None
	for i in range(len(arr)):
		if arr[i] > first:
			index = i
			break
	if index:
		a = arr[:index]
		b = arr[index:]
		print(len(a))
		for n in a:
			print(n, end=' ')
		print()
		print(len(b))
		for n in b:
			print(n, end=' ')
		print()
	else:
		print('-1')


for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	ind = -1
	for i in range(n):
		if lst[i] > lst[0]:
			ind = i
			break
	if ind != -1:
		lst1 = lst[:ind]
		lst2 = lst[ind:]
		print(len(lst1))
		for i in lst1:
			print(i, end=' ')
		print()
		print(len(lst2))
		for i in lst2:
			print(i, end=' ')
		print()
	else:
		print(-1)


t = int(input())
while t > 0:
	n = int(input())
	c = list(map(int, input().split(' ')))
	for i in c:
		if c[0] < i:
			ind = c.index(i)
			break
	else:
		print('-1')
		t -= 1
		continue
	a = c[0:ind]
	b = c[ind:]
	print(len(a))
	print(' '.join(map(str, a)))
	print(len(b))
	print(' '.join(map(str, b)))
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	f = n
	for i in range(1, n):
		if c[0] < c[i]:
			f = i
			break
	if f == n:
		print(-1)
	else:
		print(i)
		print(*c[:i])
		print(n - i)
		print(*c[i:])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = n
	for i in range(1, n):
		if a[0] < a[i]:
			f = i
			break
	if f == n:
		print(-1)
	else:
		print(i)
		print(*a[:i])
		print(n - i)
		print(*a[i:])


t = int(input())
while t:
	n = int(input())
	l = [int(x) for x in input().split()]
	f = 0
	for i in range(1, n):
		if l[i] > l[0]:
			f = 1
			break
	if f == 1:
		print(len(l[:i]))
		print(*l[:i], sep=' ')
		print(len(l[i:]))
		print(*l[i:], sep=' ')
	else:
		print(-1)
	t -= 1


T = int(input())
while T > 0:
	N = int(input())
	C = list(map(int, input().split()))
	A = []
	for i in range(len(C)):
		if i == 0:
			A.append(C[i])
		elif C[i] < C[0]:
			A.append(C[i])
		elif C[i] > C[0]:
			break
	B = C[i:]
	if len(A) == len(C):
		print(-1)
	else:
		print(len(A))
		print(*A)
		print(len(B))
		print(*B)
	T -= 1


n = int(input())
for i in range(n):
	length = int(input())
	c = [int(x) for x in input().split()]
	a = b = []
	for j in range(1, len(c)):
		if c[j] > c[0]:
			a = c[0:j]
			b = c[j:]
			break
	if len(b) == 0:
		print('-1')
	else:
		print(len(a))
		print(*a, sep=' ')
		print(len(b))
		print(*b, sep=' ')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if max(arr) == arr[0]:
		print(-1)
	else:
		m = arr[0]
		for i in range(1, n):
			if m < arr[i]:
				ind = i
				break
		print(ind)
		for i in range(ind):
			print(arr[i], end=' ')
		print()
		print(n - ind)
		for i in range(ind, n):
			print(arr[i], end=' ')
		print()


for _ in range(int(input())):
	length = int(input())
	arr = list(map(int, input().split()))
	flag = 1
	(a, b) = ([], [])
	max = arr[0]
	for num in arr:
		if num <= max and flag == 1:
			a.append(num)
		else:
			flag = 0
			b.append(num)
	if len(a) == length:
		print(-1)
	else:
		print(len(a))
		print(' '.join([str(elem) for elem in a]))
		print(len(b))
		print(' '.join([str(elem) for elem in b]))


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	m = l[0]
	k = 0
	s = []
	for i in range(n):
		if i > 0 and l[i] > m:
			k = 1
			print(i)
			print(' '.join(s))
			break
		s.append(str(l[i]))
	if k == 0:
		print(-1)
	else:
		print(n - i)
		for j in range(i, n):
			print(l[j], end=' ')
		print('')


t = int(input())
while t > 0:
	N = int(input())
	ar = list(map(int, input().split()))
	flag = 0
	for i in range(len(ar)):
		if ar[i] > ar[0]:
			flag = 1
			break
		else:
			z = i
	if flag != 1:
		print(-1)
	else:
		(i, j) = (0, 0)
		print(z + 1)
		while i <= z:
			print(ar[i], end=' ')
			i += 1
		print()
		print(len(ar) - (z + 1))
		while j < len(ar) - (z + 1):
			print(ar[j + z + 1], end=' ')
			j += 1
		print()
	t -= 1


for i in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	(a, b) = ([], [])
	mid = 0
	s = c[0]
	a.append(s)
	for j in range(1, n):
		if s < c[j]:
			mid = j
			break
		else:
			a.append(c[j])
	if mid == 0:
		print(-1)
	else:
		for p in range(mid, n):
			b.append(c[p])
		print(len(a))
		print(*a)
		print(len(b))
		print(*b)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [0] * n
	arr = [int(i) for i in input().split()]
	arr1 = []
	arr2 = []
	s = arr[0]
	arr1.append(s)
	count = 0
	for i in range(1, n, 1):
		if s < arr[i]:
			count = i
			break
		else:
			arr1.append(arr[i])
	if count != 0:
		for i in range(count, n, 1):
			arr2.append(arr[i])
		print(len(arr1))
		print(*arr1)
		print(len(arr2))
		print(*arr2)
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	c = [int(x) for x in input().split()]
	a = []
	b = []
	f = 0
	for i in range(1, n):
		if c[i] > c[0]:
			f = 1
			break
	if f == 1:
		print(len(c[:i]))
		print(*c[:i], sep=' ')
		print(len(c[i:]))
		print(*c[i:], sep=' ')
	else:
		print(-1)