| Codeforces Round 180 (Div. 1) |
|---|
| Закончено |
Белые мишки любят уникальные массивы — то есть, массивы, не содержащие повторяющихся элементов.
Вам дан уникальный массив s длиной n, состоящий из неотрицательных целых чисел. Так как Алиса и Роберт — Ваши закадычные друзья, Вы решаете разделить массив на две части. Точнее, Вам надо построить два массива a и b той же длины n, так, чтобы выполнялись следующие условия для всех i (1 ≤ i ≤ n):
- ai, bi — целые неотрицательные числа;
- si = ai + bi .
В идеале a и b также должны быть уникальными массивами. Однако в суровых арктических условиях такое не всегда возможно. К счастью, Алиса и Роберт будут рады, даже если массивы окажутся почти уникальными. Мы считаем массив длины n почти уникальным тогда и только тогда, когда его можно преобразовать в уникальный массив удалением не более чем 
элементов.
Например, массив [1, 2, 1, 3, 2] является почти уникальным, потому что после удаления первых двух элементов он становится равен [1, 3, 2]. Массив [1, 2, 1, 3, 1, 2] не является почти уникальным, потому что надо удалить по меньшей мере 3 элемента, чтобы сделать его уникальным.
Таким образом, надо разбить данный массив s на два почти уникальных массива a и b.
В первой строке входных данных содержится целое число n (1 ≤ n ≤ 105).
Во второй строке содержится n различных целых чисел s1, s2, ... sn (0 ≤ si ≤ 109).
Если возможно обрадовать Алису и Роберта (если можно разделить данный массив), выведите в первой строке «YES» (без кавычек). Во второй строке выведите массив a. В третьей строке выведите массив b. Возможно, имеется несколько решений — любое из них будет засчитано.
Если невозможно разделить s на почти уникальные массивы a и b, выведите «NO» (без кавычек) в первой строке.
6
12 5 8 3 11 9
YES
6 2 6 0 2 4
6 3 2 3 9 5
В данном примере можно удалить первые два элемента из a и второй элемент из b, чтобы сделать оба массива уникальными.
