Any sequence A of size n is called B-sequence if:
-
A1<A2<...<Ak>Ak+1>Ak+2>...>An where 1≤k≤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≤N≤105
1≤Si≤109
1≤Q≤105
1≤val≤109
Given sequence S is a B-sequence,
For 1st operation, we need to insert 5 but since 5 is the maximum element and we can have only one occurrence of maximum element in S, so we won't insert 5 in S. Size of S = 4
For 2nd operation, we need to insert 1, so we insert it in decreasing part as increasing part already has 1 in it. Size = 5
For 3rd operation, we insert 3 in increasing part. Size = 6
For 4th operation, we can't insert 2 as we already have two occurrences of it in the sequence. Size = 6
Final sequence: 1,2,3,5,2,1
