Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Toy Sum

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLittle 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:

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.

However, now Chris has exactly *s* = 10^{6} 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·10^{5}), the number of blocks in the set *X*. The next line contains *n* distinct space-separated integers *x*_{1}, *x*_{2}, ..., *x*_{n} (1 ≤ *x*_{i} ≤ 10^{6}), 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* ≤ 10^{6} - *n*), the number of blocks in the set *Y*. In the next line output *m* distinct space-separated integers *y*_{1}, *y*_{2}, ..., *y*_{m} (1 ≤ *y*_{i} ≤ 10^{6}), such that the required equality holds. The sets *X* and *Y* should not intersect, i.e. *x*_{i} ≠ *y*_{j} 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 19:18:09 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|