Any sequence A of size n is called B-sequence if:

• \(A_1 \lt A_2 \lt ... \lt A_k \gt A_{k+1} \gt A_{k+2} \gt ... \gt A_n\) where \(1 \le k \le n\). That is, a sequence which is initially strictly increasing and then strictly decreasing (the decreasing part may or may not be there).

• All elements in A except the maximum element comes atmost twice (once in increasing part and once in decreasing part) and maximum element comes exactly once.

• All elements coming in decreasing part of sequence should have come once in the increasing part of sequence.

You are given a B-sequence S and Q operations. For each operation, you are given a value val. You have to insert val in S if and only if after insertion, S still remains a B-sequence .
After each operation, print the size of S. After all the operations, print the sequence S.

Hint: Think of using some data structure to support insertion of elements in complexity better than linear.

Input Format:

First line consists of an integer N, denoting size of S.
Second line consists of N space separated integers, denoting elements of S.
Next line consists of an integer Q, denoting number of operations.
Each of the following Q lines consists of an integer val.

Output Format:

After each operation, print the size of S in a new line.
After all operations, print the sequence S.

Input Constraints:

\(1 \le N \le 10^5\)
\(1\le S_i \le 10^9\)
\(1 \le Q \le 10^5\)
\(1 \le val \le 10^9\)
Given sequence S is a B-sequence,