| Codeforces Round 238 (Div. 2) |
|---|
| Закончено |
Маленькому Крису очень нравятся игрушечные блоки. Однако его учитель хочет, чтобы Крис решал больше задач. Сегодня учитель решил пошутить над Крисом.
У Криса в наборе есть ровно s блоков, каждый блок имеет уникальный номер от 1 до s. Учитель Криса выбирает подмножество блоков X и берет его себе. Он отдаст блоки Крису, только если Крис сможет выбрать такое непустое подмножество Y из оставшихся блоков, что будет выполнено равенство:
Например, рассмотрим случай, где s = 8, а учитель Криса забрал блоки с номерами 1, 4 и 5. Крис может выбрать блоки с номерами 3 и 6 (см. рисунок). Тогда описанные суммы будут равны, как и требуется: (1 - 1) + (4 - 1) + (5 - 1) = (8 - 3) + (8 - 6) = 7.
Однако, у Криса есть ровно s = 106 блоков. Вам дано множество X из блоков, которые выбрал его учитель. Помогите Крису найти необходимое множество Y!
В первой строке входных данных записано единственное целое число n (1 ≤ n ≤ 5·105), количество блоков в множестве X. В следующей строке записано n различных целых чисел через пробел x1, x2, ..., xn (1 ≤ xi ≤ 106), номера блоков в X.
Обратите внимание: входные и выходные данные имеют очень большой размер, не стоит использовать медленные методы ввода и вывода данных вашего языка программирования. Например, в языке C++ не стоит использовать потоки ввода и вывода (cin, cout).
В первой строке выведите единственное число m (1 ≤ m ≤ 106 - n), количество блоков в множестве Y. В следующей строке выведите m различных целых чисел через пробел y1, y2, ..., ym (1 ≤ yi ≤ 106), таких, что необходимое равенство выполняется. Множества X и Y не должны пересекаться, то есть xi ≠ yj для всех i, j (1 ≤ i ≤ n; 1 ≤ j ≤ m). Гарантируется, что хотя бы одно решение всегда существует. Если существует несколько решений, выведите любое из них.
3
1 4 5
2
999993 1000000
1
1
1
1000000
