Mihai has just learned about the MEX concept and since he liked it so much, he decided to use it right away.

Given an array $a$ of $n$ non-negative integers, Mihai wants to create a new array $b$ that is formed in the following way:

While $a$ is not empty:

Choose an integer $k$ ($1 \leq k \leq |a|$).

Append the MEX of the first $k$ numbers of the array $a$ to the end of array $b$ and erase them from the array $a$, shifting the positions of the remaining numbers in $a$.

But, since Mihai loves big arrays as much as the MEX concept, he wants the new array $b$ to be the lexicographically maximum. So, Mihai asks you to tell him what the maximum array $b$ that can be created by constructing the array optimally is.

An array $x$ is lexicographically greater than an array $y$ if in the first position where $x$ and $y$ differ $x_i > y_i$ or if $|x| > |y|$ and $y$ is a prefix of $x$ (where $|x|$ denotes the size of the array $x$).

The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({${1, 2, 3}$}) $= 0$ and MEX({${0, 1, 2, 4, 5}$}) $= 3$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of elements in the array $a$.

The second line of each test case contains $n$ non-negative integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq n$), where $a_i$ is the $i$-th integer from the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print $m$ — the length of the maximum array $b$ Mihai can create, followed by $m$ integers denoting the elements of the array $b$.


-----Examples-----

Input
6
5
1 0 2 0 3
8
2 2 3 4 0 1 2 0
1
1
5
0 1 2 3 4
4
0 1 1 0
10
0 0 2 1 1 1 0 0 1 1
Output
1
4 
2
5 1 
1
0 
1
5 
2
2 2 
4
3 2 2 0


-----Note-----

In the first test case, the lexicographically maximum array $b$ is obtained by selecting $k=5$, resulting in the $MEX$ of the whole array $a$. It is lexicographically maximum because an array starting with a smaller number than $4$ is lexicographically smaller, and choosing a $k<5$ would result in an array starting with a number smaller than $4$.

In the second test case, there are two ways to obtain the maximum array: first selecting $k=6$, then $k=2$, or first selecting $k=7$ and then $k=1$.

Source: codeforces | Difficulty: MEDIUM
Tags: Constructive algorithms

Sorting

Amortized analysis

Implementation

Greedy algorithms

Mathematics


Solutions:
def solve(a):
	n = len(a)
	post_mex = [0] * n
	nums = set()
	cur_mex = 0
	for i in range(n - 1, -1, -1):
		nums.add(a[i])
		while cur_mex in nums:
			cur_mex += 1
		post_mex[i] = cur_mex
	i = j = 0
	b = []
	while i < n:
		nums = set()
		cur_mex = 0
		while i < n:
			nums.add(a[i])
			while cur_mex in nums:
				cur_mex += 1
			if cur_mex == post_mex[j]:
				break
			i += 1
		b.append(cur_mex)
		i += 1
		j = i
	return b
for _ in range(int(input())):
	input()
	b = solve(list(map(int, input().split())))
	print(len(b))
	print(' '.join(map(str, b)))


def problemC(n, arr):
	count = {}
	for num in arr:
		if num not in count:
			count[num] = 0
		count[num] += 1
	mexNumber = 0
	numBag = set()
	ans = []
	for num in arr:
		numBag.add(num)
		while mexNumber in numBag:
			mexNumber += 1
		count[num] -= 1
		if mexNumber not in count or count[mexNumber] == 0:
			ans.append(str(mexNumber))
			numBag = set()
			mexNumber = 0
	if len(numBag) >= 1:
		ans.append(str(mexNumber))
	print(len(ans))
	print(*ans)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	problemC(n, arr)


from typing import Callable, List

def read(f: Callable):
	return [f(x) for x in input().split()]

def solve(n: int, a: List[int]):
	best_mex = 0
	count_all = [0] * (n + 1)
	for x in a:
		count_all[x] += 1
		while count_all[best_mex] > 0:
			best_mex += 1
	ans = []
	count = [0] * (n + 1)
	mex = 0
	last_start = 0
	for i in range(n):
		count[a[i]] += 1
		while count[mex] > 0:
			mex += 1
		if best_mex == mex:
			ans.append(best_mex)
			for j in range(last_start, i + 1):
				x = a[j]
				count_all[x] -= 1
				count[x] -= 1
				if count_all[x] == 0 and x < best_mex:
					best_mex = x
			mex = 0
			last_start = i + 1
	print(len(ans))
	print(' '.join((str(x) for x in ans)))
for _ in range(int(input())):
	(n,) = read(int)
	a = read(int)
	solve(n, a)


import sys
input = sys.stdin.readline

def solve(n, arr):
	freq = dict()
	for i in arr:
		if i not in freq:
			freq[i] = 0
		freq[i] += 1
	ans = []
	i = 0
	while i < n:
		s = set()
		j = 0
		flag = True
		while j in s or (j in freq and freq[j] > 0):
			if j in s:
				j += 1
				continue
			freq[arr[i]] -= 1
			s.add(arr[i])
			if arr[i] == j:
				j += 1
			i += 1
			flag = False
			if i == n:
				while j in s:
					j += 1
				break
		if flag:
			i += 1
		ans.append(j)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = solve(n, arr)
	print(len(res))
	print(*res)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	i = 0
	c = [[] for i in range(n + 1)]
	for x in map(int, inp().split()):
		c[x].append(i)
		i += 1
	for i in range(n + 1):
		c[i].reverse()
	ans = []
	p = 0
	while p < n:
		m = p
		for i in range(n + 1):
			while c[i]:
				z = c[i].pop()
				if z >= p:
					m = max(m, z)
					break
			else:
				ans.append(i)
				break
		p = m + 1
	print(len(ans))
	print(' '.join(map(str, ans)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	nums = set()
	rem = Counter(a)
	mex = 0
	for num in a:
		nums.add(num)
		rem[num] -= 1
		while mex in nums:
			mex += 1
		if not rem[mex]:
			ans.append(mex)
			nums = set()
			mex = 0
	print(len(ans))
	print(*ans)


from collections import Counter

def solve(A):
	counts = Counter(A)
	p = 0
	ret = []
	while p < len(A):
		upto = 0
		while counts[upto]:
			upto += 1
		ret.append(upto)
		found = [False] * upto
		left = upto
		while True:
			if A[p] < upto and (not found[A[p]]):
				found[A[p]] = True
				left -= 1
			counts[A[p]] -= 1
			p += 1
			if not left:
				break
	print(len(ret))
	print(*ret)
	return ret
t = int(input())
for _ in range(t):
	_ = input()
	A = [int(x) for x in input().split()]
	solve(A)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	left = Counter(a)
	c = set()
	ans = []
	mex = 0
	for i in range(n):
		c.add(a[i])
		while mex in c:
			mex += 1
		if left[mex] == 0:
			ans.append(mex)
			c.clear()
			mex = 0
		left[a[i]] -= 1
	print(len(ans))
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	sufMex = [0] * n
	s = {a[-1]}
	mex = 0
	while mex in s:
		mex += 1
	for i in range(n - 2, -1, -1):
		sufMex[i] = mex
		s.add(a[i])
		while mex in s:
			mex += 1
	target = mex
	mex = 0
	numSet = set()
	for i in range(n):
		numSet.add(a[i])
		while mex in numSet:
			mex += 1
		if target == mex:
			ans.append(mex)
			target = sufMex[i]
			mex = 0
			numSet.clear()
	if len(numSet) > 0:
		ans.append(mex)
	print(len(ans))
	print(*ans)


import sys
from collections import Counter
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def inp():
	return int(input())

def read_int_list():
	return list(map(int, input().split()))

def find_mex(freq):
	for (index, f) in enumerate(freq):
		if f == 0:
			return index

def solve(a):
	freq = [0] * (len(a) + 1)
	for value in a:
		freq[value] += 1
	mex = find_mex(freq)
	res = [mex]
	i = 0
	while i < len(a):
		to_remove = mex
		if mex == 0:
			to_remove = 1
		touched = set()
		while to_remove > 0 and i < len(a):
			value = a[i]
			freq[value] -= 1
			if value < mex and value not in touched:
				touched.add(value)
				to_remove -= 1
			i += 1
			if mex == 0:
				break
		if i < len(a):
			mex = find_mex(freq)
			res.append(mex)
	print(len(res))
	print(*res)
for _ in range(inp()):
	_ = inp()
	a = read_int_list()
	solve(a)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	count = Counter(lst)
	a_set = set()
	mex = 0
	b = []
	for j in lst:
		count[j] -= 1
		a_set.add(j)
		while mex in a_set:
			mex += 1
		if count[mex] == 0:
			b.append(mex)
			a_set.clear()
			mex = 0
	print(len(b))
	print(*b)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	mex_f = []
	curr_mex = 0
	seen = {}
	for i in range(n - 1, -1, -1):
		seen[arr[i]] = True
		if curr_mex in seen:
			while curr_mex in seen:
				curr_mex += 1
		mex_f.append(curr_mex)
	mex_f = mex_f[::-1]
	ans = []
	i = 0
	while i < n:
		mz = 0
		seen = {}
		for j in range(i, n):
			seen[arr[j]] = True
			while mz in seen:
				mz += 1
			if mz == mex_f[i]:
				ans.append(mz)
				i = j + 1
				break
	print(len(ans))
	ans = [str(i) for i in ans]
	print(' '.join(ans))


import sys
import re
import math
from math import log2 as lg
from math import gcd
from decimal import *
from collections import deque
import random
import heapq
import itertools
import datetime
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	m = int(input())
	lst = get()
	d = {}
	for term in lst:
		if term in d:
			d[term] += 1
		else:
			d[term] = 1
	mex = 0
	store = {}
	ans = []
	j = 0
	while j < m:
		if mex in d and d[mex] > 0:
			while lst[j] != mex:
				curr = lst[j]
				store[curr] = 0
				d[curr] -= 1
				j += 1
			store[lst[j]] = 0
			d[lst[j]] -= 1
			j += 1
			while mex in store:
				mex += 1
		elif mex == 0:
			break
		else:
			ans.append(mex)
			mex = 0
			store = {}
	if mex > 0:
		ans.append(mex)
	while j < m:
		ans.append(0)
		j += 1
	print(len(ans))
	ans = list(map(str, ans))
	print(' '.join(ans))


for _ in range(int(input())):
	n = int(input())
	aa = [int(a) for a in input().split()]
	mx = 0
	mexs = [0] * n
	found = set()
	for (i, a) in enumerate(aa[::-1], 1):
		found.add(a)
		if a == mx:
			while mx in found:
				mx += 1
		mexs[-i] = mx
	res = []
	mx = 0
	found = set()
	lp = 0
	for (i, a) in enumerate(aa):
		found.add(a)
		if a == mx:
			while mx in found:
				mx += 1
		if mx == mexs[lp]:
			res.append(mx)
			mx = 0
			found.clear()
			lp = i + 1
	print(len(res))
	print(*res)


import sys
input = sys.stdin.readline
suffix = [0] * (2 * 10 ** 5 + 1)

def find_first(p):
	exist = dict()
	mex = 0
	for i in range(p, n):
		exist[a[i]] = 1
		while mex in exist:
			mex += 1
		if mex == suffix[p]:
			return i
	return n
for _ in range(int(input().strip())):
	exist = [0] * (2 * 10 ** 5 + 1)
	n = int(input().strip())
	a = list(map(int, input().split()))
	mex = 0
	b = []
	for i in reversed(range(n)):
		exist[a[i]] = 1
		while exist[mex]:
			mex += 1
		suffix[i] = mex
	p = 0
	while p < n:
		b.append(suffix[p])
		p = find_first(p) + 1
	print(len(b))
	print(*b)


for w in range(0, int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	counts = [0] * (n + 1)
	for x in arr:
		counts[x] += 1
	b = []
	p = 0
	target = counts.index(0)
	while p < n:
		found = [False] * target
		s = 0
		new_target = target
		if target == 0:
			e = arr[p]
			counts[e] -= 1
			p += 1
		while s < target:
			e = arr[p]
			counts[e] -= 1
			if counts[e] == 0:
				new_target = min(new_target, e)
			if e < target and (not found[e]):
				found[e] = True
				s += 1
			p += 1
			if p == n:
				break
		if s == target:
			b.append(target)
		else:
			b.append(found.index(False))
		target = new_target
	print(len(b))
	print(' '.join((str(x) for x in b)))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	suf = [0 for i in range(n + 1)]
	s = set()
	for i in range(n - 1, -1, -1):
		suf[i] = suf[i + 1]
		s.add(a[i])
		while suf[i] in s:
			suf[i] += 1
	i = 0
	b = []
	while i < n:
		s = set()
		mex = 0
		for j in range(i, n):
			s.add(a[j])
			while mex in s:
				mex += 1
			if mex == suf[i]:
				b.append(mex)
				i = j + 1
				break
	print(len(b))
	print(' '.join(map(str, b)))


import math
mod = 998244353

def catalan(n):
	return int(math.factorial(2 * n) // (math.factorial(n) * math.factorial(n + 1))) % mod

def C(n, k):
	return math.comb(n, k)

def binpow(a, n):
	if n == 0:
		return 1 % mod
	x = binpow(a, n // 2)
	if n % 2 == 0:
		return x * x % mod
	else:
		return x * x * a % mod
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	rem = Counter(a)
	c = set()
	ans = []
	mex = 0
	for i in range(n):
		c.add(a[i])
		while mex in c:
			mex += 1
		if rem[mex] == 0:
			ans.append(mex)
			c.clear()
			mex = 0
		rem[a[i]] -= 1
	print(len(ans))
	print(*ans)


from collections import Counter
for iii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	rem = Counter(q)
	c = set()
	ans = []
	mex = 0
	for i in range(n):
		c.add(q[i])
		while mex in c:
			mex += 1
		if rem[mex] == 0:
			ans.append(mex)
			c.clear()
			mex = 0
		rem[q[i]] -= 1
	print(len(ans))
	print(*ans)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set()
	data = Counter(a)
	m = 0
	b = []
	for i in range(n):
		s.add(a[i])
		while m in s:
			m += 1
		if data[m] == 0:
			b.append(m)
			m = 0
			s.clear()
		data[a[i]] -= 1
	print(len(b))
	print(*b)


ans = []
razm = []
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	used = [0] * (n + 2)
	ok = [0] * (n + 2)
	num = 1
	for i in range(n):
		used[x[i]] += 1
	for i in range(n + 2):
		if used[i] == 0:
			k = i - 1
			break
	k1 = k
	otv = []
	j = 0
	for i in range(n):
		used[x[i]] -= 1
		if x[i] <= k1 and used[x[i]] == 0:
			k1 = x[i] - 1
		ok[x[i]] = num
		while ok[j] == num:
			j += 1
		if k + 1 == j:
			otv.append(k + 1)
			k = k1
			num += 1
			j = 0
	razm.append(len(otv))
	ans.append(otv)
for i in range(len(ans)):
	print(razm[i])
	print(' '.join([str(j) for j in ans[i]]))


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
for _ in [0] * int(input()):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = [0] * (n + 2)
	for i in range(n):
		c[a[i]] += 1
	for i in range(n + 2):
		if c[i] == 0:
			mex = nmex = i
			break
	s = set()
	check = 0
	for i in range(n):
		if len(s) == mex and check:
			b += [mex]
			mex = nmex
			s = set()
			check = 0
		if a[i] < mex:
			s.add(a[i])
		c[a[i]] -= 1
		if c[a[i]] == 0:
			nmex = min(nmex, a[i])
		check = 1
	if len(s) == mex and check:
		b += [mex]
	print(len(b))
	print(*b)


from collections import deque

def mex(l):
	m = max(l)
	res = set([i for i in range(m + 2)])
	for i in l:
		if i in res:
			res.remove(i)
	return min(res)

def foo(l, mex):
	if mex == 0:
		l.popleft()
		return (l, mex)
	res = set([i for i in range(mex)])
	while l:
		if not res:
			break
		else:
			k = l.popleft()
			d[k] -= 1
			if d[k] == 0:
				del d[k]
				mex = min(mex, k)
			if k in res:
				res.remove(k)
	return (l, mex)
for _ in range(int(input())):
	n = int(input())
	l = deque(list(map(int, input().split())))
	ans = []
	d = {}
	for i in l:
		d[i] = d.get(i, 0) + 1
	m = mex(l)
	while l:
		ans.append(m)
		(l, m) = foo(l, m)
	print(len(ans))
	print(*ans)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = [0] * (n + 1)
	for x in a:
		cnt[x] += 1
	p = 0
	ans = []
	while p < n:
		mex = 0
		while cnt[mex] > 0:
			mex += 1
		ans.append(mex)
		used = [False] * mex
		cnt_used = 0
		while True:
			if a[p] < mex and (not used[a[p]]):
				used[a[p]] = True
				cnt_used += 1
			cnt[a[p]] -= 1
			p += 1
			if cnt_used == mex:
				break
	print(len(ans))
	print(*ans)


from collections import Counter
for iiii in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	q1 = Counter(q)
	s = set()
	cou = 0
	q2 = []
	for i in range(n):
		s.add(q[i])
		q1[q[i]] -= 1
		while cou in s:
			cou += 1
		if cou not in q1 or q1[cou] == 0:
			q2.append(cou)
			s = set()
			cou = 0
	print(len(q2))
	print(*q2)


import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	arr = [int(x) for x in input().split()]
	n = len(arr)
	indices = dict()
	for i in range(len(arr) - 1, -1, -1):
		x = arr[i]
		if x not in indices:
			indices[x] = [i]
		else:
			indices[x] += [i]
	ans = []
	i_start = 0
	while i_start < n:
		i_end = i_start
		mex = 0
		while mex in indices and indices[mex]:
			j = indices[mex].pop()
			if j < i_start:
				continue
			i_end = max(i_end, j)
			mex += 1
		ans += [mex]
		i_start = i_end + 1
	print(len(ans))
	print(*ans)


def f(n, arr):
	dct = {}
	for (i, k) in enumerate(arr):
		if k not in dct:
			dct[k] = set()
		dct[k].add(i)
	s_arr = sorted(arr)
	if s_arr[0] != 0:
		m = 0
		print(n)
		print(' '.join(['0'] * n))
		return
	else:
		for i in range(1, n):
			if s_arr[i] - s_arr[i - 1] > 1:
				m = s_arr[i - 1] + 1
				break
		else:
			m = s_arr[-1] + 1
	res = []
	new_m = None
	current = set()
	for (i, k) in enumerate(arr):
		if m == 0:
			res.append(0)
			continue
		if k < m:
			current.add(k)
		dct[k].remove(i)
		if len(dct[k]) == 0 and k < m and (new_m is None or k < new_m):
			new_m = k
		if len(current) == m:
			res.append(m)
			current.clear()
			if new_m is not None:
				m = new_m
	if len(current) > 0:
		res.append(m)
	print(len(res))
	print(' '.join(map(str, res)))
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	f(n, arr)


from collections import Counter

def mex_array():
	mex_arr_val = 0
	while mex_arr_val <= n:
		if mex_arr_val not in set_arr:
			return mex_arr_val
		mex_arr_val += 1
	return mex_arr_val
for _ in range(int(input())):
	n = int(input())
	arr = [int(item) for item in input().split()]
	cnt = Counter(arr)
	set_arr = set(arr)
	ans = []
	i = 0
	while i < n:
		m_mex = mex_array()
		s_set = set()
		while i < n:
			if arr[i] < m_mex:
				s_set.add(arr[i])
			cnt[arr[i]] -= 1
			if cnt[arr[i]] == 0:
				set_arr.remove(arr[i])
			if len(s_set) == m_mex:
				break
			i += 1
		ans.append(m_mex)
		i += 1
	print(len(ans))
	print(*ans)


from collections import Counter

def mex():
	mex_val = 0
	while mex_val <= n:
		if mex_val not in s:
			return mex_val
		mex_val += 1
	return mex_val
for _ in range(int(input())):
	n = int(input())
	arr = [int(item) for item in input().split()]
	c = Counter(arr)
	s = set(arr)
	ans = []
	i = 0
	while i < n:
		m = mex()
		z = set()
		while i < n:
			if arr[i] < m:
				z.add(arr[i])
			c[arr[i]] -= 1
			if c[arr[i]] == 0:
				s.remove(arr[i])
			if len(z) == m:
				break
			i += 1
		ans.append(m)
		i += 1
	print(len(ans))
	print(*ans)


import collections
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	h = dict(collections.Counter(a))
	mex = -1
	m = max(a)
	for i in range(m + 2):
		if not i in h:
			mex = i
			break
	curr = mex
	i = 0
	b = []
	while i < n:
		if mex == 0:
			while i < n:
				b.append(0)
				i += 1
			break
		k = set()
		for j in range(mex):
			k.add(j)
		while i < n and len(k) > 0:
			if a[i] in k:
				k.remove(a[i])
			h[a[i]] -= 1
			if h[a[i]] == 0 and a[i] < curr:
				curr = a[i]
			i += 1
		if len(k) == 0:
			b.append(mex)
		else:
			for j in range(mex + 1):
				if not j in k:
					b.append(j)
					break
		mex = curr
	print(len(b))
	for i in b:
		print(i, end=' ')
	print()


import sys
from math import *
from math import *
from functools import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	h = {}
	for i in a:
		h[i] = h.get(i, 0) + 1
	i = 0
	j = 0
	s = set()
	k = 0
	while i < n:
		if j in h:
			if h[j] > 1:
				h[j] -= 1
			else:
				h.pop(j)
			while i < n and a[i] != j:
				if h[a[i]] > 1:
					h[a[i]] -= 1
				else:
					h.pop(a[i])
				s.add(a[i])
				i += 1
			s.add(j)
			while k in s:
				k += 1
			j = k
			i += 1
		else:
			if j == 0:
				i += 1
			b.append(j)
			j = 0
			k = 0
			s = set()
	if j != 0:
		b.append(j)
	print(len(b))
	print(*b)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = []
	d = {}
	for i in range(len(arr)):
		if arr[i] in d:
			d[arr[i]] += 1
		else:
			d[arr[i]] = 1
	index = 0
	while True:
		mex = 0
		for i in range(len(d) + 1):
			if i not in d:
				mex = i
				ans.append(i)
				break
		temp = {}
		index2 = index
		iszero = False
		for i in range(index, len(arr)):
			if arr[i] not in temp and arr[i] < mex:
				temp[arr[i]] = 1
			if arr[i] in d:
				d[arr[i]] -= 1
			if d[arr[i]] <= 0:
				d.pop(arr[i])
			if len(temp) >= mex:
				break
			index2 += 1
		index = index2 + 1
		if index >= n:
			break
	print(len(ans))
	for i in ans:
		print(i, end=' ')
	print()
	return
for _ in range(int(input())):
	solve()


import math
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	s = set()
	rev = A[::-1]
	dp = [0] * n
	curr = 0
	for i in range(n):
		d[rev[i]] += 1
		while d[curr] > 0:
			curr += 1
		dp[i] = curr
	dp = dp[::-1]
	i = 0
	st = 0
	ans = []
	last = False
	while i < n:
		while i < n and len(s) < dp[st]:
			if A[i] < dp[st]:
				s.add(A[i])
			last = True
			i += 1
		if len(s) == dp[st]:
			s = set()
			ans.append(dp[st])
			if i < n:
				st = i
		if not last:
			i += 1
		last = False
	print(len(ans))
	print(*ans)


n = int(input())
for _ in range(n):
	m = int(input())
	numbers = list(map(int, input().split()))
	counter = [0] * (m + 1)
	for number in numbers:
		counter[number] += 1
	answer = []
	index = 0
	while True:
		mex = 0
		while counter[mex] > 0:
			mex += 1
		answer.append(mex)
		used = [False] * mex
		if mex == 0:
			counter[numbers[index]] -= 1
			index += 1
		while mex and index < m:
			if numbers[index] < len(used) and (not used[numbers[index]]):
				used[numbers[index]] = True
				mex -= 1
			counter[numbers[index]] -= 1
			index += 1
		if index >= m:
			break
	print(len(answer))
	print(*answer)


for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	suffix_mex = [0] * (n + 1)
	s = set()
	for i in range(n - 1, -1, -1):
		suffix_mex[i] = suffix_mex[i + 1]
		s.add(x[i])
		while suffix_mex[i] in s:
			suffix_mex[i] += 1
	idx = 0
	ans = []
	while idx < n:
		s = set()
		temp = 0
		for j in range(idx, n):
			s.add(x[j])
			while temp in s:
				temp += 1
			if temp == suffix_mex[idx]:
				ans.append(temp)
				idx = j + 1
				break
	print(len(ans))
	print(*ans)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	n = I()
	a = L()
	b = []
	d = {}
	cur = 0
	for i in range(n):
		d[a[i]] = d.get(a[i], 0) + 1
	for i in range(n + 1):
		if d.get(i, 0) == 0:
			cur = i
			break
	i = 0
	while i < n:
		if cur == 0:
			i += 1
			b.append(cur)
			continue
		j = i
		m = cur
		s = set()
		while j < n:
			if len(s) == cur:
				break
			d[a[j]] -= 1
			if d[a[j]] == 0:
				m = min(m, a[j])
			if a[j] < cur and a[j] not in s:
				s.add(a[j])
			j += 1
		b.append(cur)
		i = j
		cur = m
	print(len(b))
	print(*b)


for lll in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = [0] * 200001
	for j in range(n):
		c[a[j]] += 1
	t = 0
	i = 0
	while t == 0:
		cc = 0
		while c[cc] > 0:
			cc += 1
		if cc == 0:
			t = 1
			for k in range(n - i):
				b.append(0)
			break
		else:
			b.append(cc)
			dc = [1] * cc
			nc = cc
			while i < n:
				if a[i] < cc:
					if dc[a[i]] == 1:
						dc[a[i]] = 0
						nc -= 1
				c[a[i]] -= 1
				i += 1
				if nc == 0:
					break
			if i == n:
				break
	print(len(b))
	print(*b)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	data = {}
	ans = []
	for i in range(n):
		if a[i] not in data:
			data[a[i]] = deque()
			data[a[i]].appendleft(i)
		else:
			data[a[i]].appendleft(i)
	idx = -1
	while idx < n - 1:
		mex = 0
		idx2 = idx
		while mex in data and data[mex]:
			get = data[mex].pop()
			if get > idx:
				idx2 = max(idx2, get)
				mex += 1
		idx = idx2
		if mex:
			ans.append(mex)
		else:
			ans += [0] * (n - idx - 1)
			break
	print(len(ans))
	print(*ans)


import sys
from collections import deque

def rl():
	return sys.stdin.readline().rstrip()

def ri():
	return int(rl())

def ril():
	return [int(x) for x in rl().split(' ')]

def main():
	t = ri()
	for _ in range(t):
		n = ri()
		a_arr = ril()
		occs = [deque([]) for _ in range(n + 1)]
		for (idx, a) in enumerate(a_arr):
			occs[a].append(idx)
		b_arr = []
		cur_idx = 0
		next_idx = cur_idx
		while cur_idx < n:
			for val in range(n + 1):
				while len(occs[val]) > 0 and occs[val][0] < cur_idx:
					occs[val].popleft()
				if len(occs[val]) == 0:
					b_arr.append(val)
					cur_idx = next_idx + 1
					next_idx = cur_idx
					break
				else:
					next_idx = max(next_idx, occs[val][0])
		print(len(b_arr))
		print(' '.join([str(x) for x in b_arr]))
main()


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	i = 0
	counter = Counter(l)
	while i < n:
		j = 0
		while j in counter and counter[j] > 0:
			j += 1
		ans.append(j)
		sett = set()
		if j == 0:
			counter[l[i]] -= 1
			i += 1
		while len(sett) < j:
			if l[i] < j:
				sett.add(l[i])
				counter[l[i]] -= 1
			i += 1
		j = 0
		sett.clear()
	print(len(ans))
	print(*ans)


from collections import defaultdict

def solve(arr):
	places = defaultdict(list)
	pointer = {}
	for i in range(len(arr)):
		places[arr[i]].append(i)
		pointer[arr[i]] = 0
	if places[0] == []:
		return [0 for _ in range(len(arr))]
	res = []
	starting_point = 0
	while starting_point < len(arr):
		while pointer.get(0, 0) < len(places[0]) and places[0][pointer[0]] < starting_point:
			pointer[0] += 1
		if pointer.get(0, 0) >= len(places[0]):
			res.append(0)
			starting_point += 1
			continue
		end_position = starting_point
		new_val = 0
		for num in range(0, 10 ** 7):
			p = pointer.get(num, -1)
			if p == -1:
				break
			while p < len(places[num]) and places[num][p] < starting_point:
				p += 1
			pointer[num] = p
			if p == len(places[num]):
				break
			end_position = max(end_position, places[num][p])
			new_val = num
		res.append(new_val + 1)
		starting_point = end_position + 1
	return res
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	solution = solve(arr)
	print(len(solution))
	print(' '.join(map(str, solution)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = [[] for _ in range(n + 1)]
	for i in range(n):
		ind[a[i]].append(i)
	for i in range(n + 1):
		ind[i].reverse()
	mex = 0
	while ind[mex]:
		mex += 1
	start = 0
	b = []
	while start < n and mex > 0:
		b.append(mex)
		end = start
		for j in range(mex):
			end = max(end, ind[j][-1])
		for j in range(mex):
			while ind[j] and ind[j][-1] <= end:
				ind[j].pop()
			if not ind[j]:
				mex = min(mex, j)
		start = end + 1
	if start < n:
		b += [0] * (n - start)
	print(len(b))
	print(*b)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	deques = []
	for i in range(n + 1):
		deques.append(deque())
	for i in range(n):
		deques[arr[i]].append(i)
	res = []
	lastInd = -1
	while True:
		index = -1
		last = -1
		for i in range(n):
			if deques[i]:
				index = max(index, deques[i][0])
				last = i
			else:
				break
		for i in range(0, last + 1):
			while deques[i] and deques[i][0] <= index:
				deques[i].popleft()
		if last == -1:
			for i in range(n - lastInd - 1):
				res.append(0)
			break
		else:
			res.append(last + 1)
			lastInd = index
	size = res.__len__()
	print(size)
	for i in range(size):
		print(res[i], end=' ')
	print()


import sys
from collections import deque
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	d = [deque() for i in range(n + 1)]
	for i in range(n):
		d[a[i]].append(i)
	(ans, s) = ([], 0)
	while s < n:
		(m, mex) = (s, 0)
		for i in range(n + 1):
			if len(d[i]) == 0:
				break
			m = max(m, d[i][0])
			mex += 1
		ans.append(mex)
		for i in range(s, m + 1):
			d[a[i]].popleft()
		s = m + 1
	print(len(ans))
	print(*ans)


import time
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	data = {}
	ans = []
	for i in range(n):
		if a[i] not in data:
			data[a[i]] = [i]
		else:
			data[a[i]].append(i)
	idx = -1
	while idx < n - 1:
		mex = 0
		idx2 = idx
		while mex in data and data[mex] != []:
			if data[mex][0] <= idx:
				del data[mex][0]
			else:
				idx2 = max(idx2, data[mex][0])
				mex += 1
		idx = idx2
		if mex:
			ans.append(mex)
		else:
			ans += [0] * (n - idx - 1)
			break
	print(len(ans))
	print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	d = [0] * 200001
	mex_from_last = [0 for i in range(n)]
	curr_mex = 0
	for i in range(n - 1, -1, -1):
		d[a[i]] = 1
		while d[curr_mex]:
			curr_mex += 1
		mex_from_last[i] = curr_mex
	b = []
	d = [0] * 200001
	curr_mex = 0
	target = mex_from_last[0]
	s = []
	for i in range(n):
		s.append(a[i])
		d[a[i]] += 1
		while d[curr_mex]:
			curr_mex += 1
		if curr_mex == target:
			b.append(target)
			while s:
				d[s.pop()] -= 1
			curr_mex = 0
			if i != n - 1:
				target = mex_from_last[i + 1]
		elif i == n - 1:
			b.append(0)
	print(len(b))
	print(*b)