Little Chris is very keen on his toy blocks. His teacher, however, wants Chris to solve more problems, so he decided to play a trick on Chris.

There are exactly s blocks in Chris's set, each block has a unique number from 1 to s. Chris's teacher picks a subset of blocks X and keeps it to himself. He will give them back only if Chris can pick such a non-empty subset Y from the remaining blocks, that the equality holds: 

<image> "Are you kidding me?", asks Chris.

For example, consider a case where s = 8 and Chris's teacher took the blocks with numbers 1, 4 and 5. One way for Chris to choose a set is to pick the blocks with numbers 3 and 6, see figure. Then the required sums would be equal: (1 - 1) + (4 - 1) + (5 - 1) = (8 - 3) + (8 - 6) = 7.

<image>

However, now Chris has exactly s = 106 blocks. Given the set X of blocks his teacher chooses, help Chris to find the required set Y!

Input

The first line of input contains a single integer n (1 ≤ n ≤ 5·105), the number of blocks in the set X. The next line contains n distinct space-separated integers x1, x2, ..., xn (1 ≤ xi ≤ 106), the numbers of the blocks in X.

Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.

Output

In the first line of output print a single integer m (1 ≤ m ≤ 106 - n), the number of blocks in the set Y. In the next line output m distinct space-separated integers y1, y2, ..., ym (1 ≤ yi ≤ 106), such that the required equality holds. The sets X and Y should not intersect, i.e. xi ≠ yj for all i, j (1 ≤ i ≤ n; 1 ≤ j ≤ m). It is guaranteed that at least one solution always exists. If there are multiple solutions, output any of them.

Examples

Input

3
1 4 5


Output

2
999993 1000000

Input

1
1


Output

1
1000000

Difficulty: MEDIUM_HARD
Tags: Mathematics

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n,) = I()
a = I()
M = 10 ** 6 + 1
take = [0] * M
for i in a:
	take[i] = 1
ans = []
ok = []
cnt = 0
for i in range(1, M // 2 + 1):
	if take[i] and take[M - i]:
		cnt += 1
	elif not take[i] and (not take[M - i]):
		ok.append((i, M - i))
	elif take[i]:
		ans.append(M - i)
	else:
		ans.append(i)
for i in range(cnt):
	ans.append(ok[i][0])
	ans.append(ok[i][1])
print(len(ans))
print(*ans)


import sys
from math import gcd, sqrt, ceil
from collections import defaultdict, Counter, deque
import math
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)
n = int(input())
l = list(map(int, input().split()))
s = 10 ** 6
ans = set()
l = set(l)
w = 0
for i in range(1, s + 1):
	opp = s + 1 - i
	if i in l and opp not in l:
		ans.add(opp)
	elif i in l and opp in l:
		w += 1
w //= 2
for i in range(1, s + 1):
	opp = s + 1 - i
	if w == 0:
		break
	if opp not in ans and i not in ans and (i not in l) and (opp not in l):
		ans.add(opp)
		ans.add(i)
		w -= 1
print(len(ans))
print(*ans)


n = int(input())
l = [int(i) for i in list(input().split())]
size = 10 ** 6
mask = [0] * (size + 1)
for i in l:
	mask[i] = 1
counter = 0
result = []
for i in range(1, size + 1):
	if mask[i] == 1 and mask[size + 1 - i] == 0:
		mask[size + 1 - i] = 2
		result.append(size + 1 - i)
	elif mask[i] == 1 and mask[size + 1 - i] == 1:
		counter += 1
		mask[size + 1 - i] = 2
	elif mask[i] == 0 and mask[size + 1 - i] == 0 and (counter > 0):
		mask[i] = 2
		mask[size + 1 - i] = 2
		result.append(i)
		result.append(size + 1 - i)
		counter -= 1
print(len(result))
print(*result)


import sys

def solve():
	n = int(input())
	s = 1000000
	xset = set(map(int, input().split()))
	res = set()
	wantother = 0
	for i in range(1, s + 1):
		opposite = s - i + 1
		if i in xset:
			if opposite not in xset:
				res.add(opposite)
			else:
				wantother += 1
	wantother /= 2
	for i in range(1, s + 1):
		if wantother == 0:
			break
		opposite = s - i + 1
		if i not in res and i not in xset and (opposite not in xset):
			res.add(i)
			res.add(opposite)
			wantother -= 1
	print(len(res))
	return ' '.join(map(str, res))
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
print(solve())