Hard Sum Set Problem
/

## Algorithms, Linear search, Searching algorithm

Problem
Editorial
Analytics

Consider two sets $A$ and $B$, let define their sum set $S(A, B) = \{a + b | a \in A, b\in B\}$. Now given a set $C$, your task is to find two sets $A$ and $B$ such that $50 \le |A|, 50 \le |B|, |C| \le |S(A, B)|$.

Assumption, $C = \{c_1, c_2, ..., c_n\}, S(A, B) = \{s_1, s_2, ..., s_m\}, c_1 < c_2 < \dots < c_n, s_1 < s_2 < \dots < s_m$. We define the score as: $\sum_{i = 0}^{m - n}{\sum_{j = 1}^{n}{|c_j - s_{j + i}|}}$. You are asked to minimize the score.

Input

The first line contains an integer $K$ denoting the number of elements of set $C$.

The following line contains $K$ space-separated integers $c_1, c_2, \dots, c_K$ denoting the elements of set $C$.

Output

Output four lines:

• The first line contains an integer $N$, the number of elements of set $A$.
• The second line contains $N$ space-separated integers $a_1, a_2, \dots, a_N$, the elements of set $A$.
• The third line contains an integer $M$, the number of elements of set $B$.
• The forth line contains $M$ space-separated integers $b_1, b_2, \dots, b_M$, the elements of set $B$.

Constraints

• $1\le K \le 5000$.
• $50\le N, M \le 5000$.
• $1 \le c_i, a_i, b_i \le 5000$.

Data generation:

• 25% tests: each number from 1 to $5000$ has probability in set C is $\frac{1}{2}$.
• 25% tests: each number from 1 to $5000$ has probability in set C is $\frac{1}{3}$.
SAMPLE INPUT
4
6 8 9 11


SAMPLE OUTPUT
2
2 4
2
4 7


Explanation

Note that: The constraints on the number of elements of each set is ignored in this example.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...