Stacks of Slices Solution

Problem

Chef has a set of $N$ slices of bread which he wants to arrange in stacks. The stacks should be stable. A stable stack is one in which the slices in a single stack are ordered by their radii in a strictly increasing order such that the top-most slice will have the smallest radius. For example, a stack of slices with radii $[7, 4, 3]$ is stable, while a stack of slices with radii $[3, 5, 2]$ is not.

Chef has come up with the following algorithm to arrange the slices after the order of slices is given:

• First, Chef initiates an empty set of slice stacks.
• Then, Chef processes the disks in the chosen order using the following pattern:
  • If there is at least one stack such that Chef can put the current slice on the top of the stack without making it unstable, then he chooses the stack with the smallest top slice radius strictly greater than the radius of the current slice and puts the current slice on top of that stack.
  • Otherwise, Chef makes a new stack containing only the current slice.

For example, let the order of slices be given by $[4,7,9,3,1,2]$, then the algorithm will be run in the following way:

• At the beginning of the algorithm, the set of slice stacks is empty. After processing the first slice, the set of top stack slices is $[4]$.
• The 2nd slice can't be put on top of the first stack, hence Chef will need a new one. The set of top stack slices becomes $[4,7]$.
• Similarly, the 3rd slice can't be put in any of the existing stacks, hence Chef will make a new one. The set of top stack slices becomes $[4,7,9]$.
• The 4th slice can be put on top of the first one, as the first stack is the smallest radius stack that is greater than the current slice radius. The set now becomes $[3,7,9]$.
• The 5th and 6th slices can be put on top of stack 2nd and 3rd respectively. The final set is $[3,1,2]$.

Chef is busy and can't arrange the slices of bread, hence he asks for your help. Given a list of $N$ radii of slices $R_i$, print the final set of top stack slices that will be present after arranging the slices according to the above algorithm.

Input Format

• The first line of the input contains an integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of a test description contains a single integer $N$.
• The second line of the description contains $N$ integers denoting $R_1$, $R_2$, ..., $R_N$.

Output Format

For each test case, output a single line. The line should start with a positive integer $S$ denoting the number of stacks after the algorithm is done. This should be followed by $S$ integers on the same line denoting the stacks' top slice radii in non-decreasing order.

If there are multiple correct answers, you are allowed to output any of them.

Constraints

• $1 \leq T \leq 10$
• $1 \leq N \leq 10^5$
• $1 \leq R_i \leq 10^9$

Sample 1:

Input

Output

4
6
4 7 9 3 1 2
6
3 4 5 1 1 2
10
3 2 9 5 2 9 4 14 7 10
8
14 5 13 19 17 10 18 12

3 3 1 2
3 1 1 2
5 2 2 4 7 10 
4 5 10 12 18

Explanation:

Sample test 1 is already explained in the problem statement.

Program :

#include<stdio.h>

int main()

{

int t,n,a[100000],i,p,count[100000];

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

int l,r,m;

p=1;

count[0]=a[0];

for(i=1;i<n;i++)

{

 

if(a[i]>=count[p-1])

{

count[p++]=a[i];

}

else

{

l=0;

r=p;

while(r>l)

{

m=(l+r)/2;

if(count[m]>a[i])

r=m;

else

l=m+1;

}

count[l]=a[i];

}

}

printf("%d ",p);

for(i=0;i<p;i++)

{

printf("%d ",count[i]);

}

printf("\n");

}

return 0;

}