Fun Game

 Problem:-

 and $B$  are playing a game. In this game, both of them are initially provided with a list of $n$ numbers. (Both have the same list but their own copy).

Now, they both have a different strategy to play the game. $A$ picks the element from start of his list. $B$ picks from the end of his list.

You need to generate the result in form of an output list.

Method to be followed at each step to build the output list is:

1. If the number picked by $A$ is bigger than $B$ then this step's output is $1$ . $B$ removes the number that was picked from their list.
2. If the number picked by $A$ is smaller than $B$ then this step's output is $2$ . $A$ removes the number that was picked from their list.
3. If both have the same number then this step's output is $0$ . Both $A$ and $B$  remove the number that was picked from their list.

This game ends when at least one of them has no more elements to be picked i.e. when the list gets empty.

Output the built output list.
  

Input format:

First line consists of a number $n$ , size of the list provided.
Next line consists of $n$ numbers separated by space.

Output format:

Output the required output list.

Constraints:

$1\le N\le {10}^6$
$1\le numbersinthelist\le {10}^9$

 

Sample Input

3
1 2 3

Sample Output

2 2 0

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

1st step: A picks 1. B picks 3. B > A. So output is 2. A removes 1.
2nd step: A picks 2. B picks 3. B > A. So output is 2. A removes 2.
3rd step: A picks 3. B picks 3. B = A. So output is 0. A removes 3. B removes 3.

Output list: [2, 2, 0]

Code:-

#include<stdio.h>

# define max 1000000

long long int stack[max];

long int top1=-1;

long int top2=0;

int main()

{

long int n,i,element,element1;

scanf("%ld",&n);

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

{

scanf("%lld",&element);

top1=top1+1;

stack[top1]=element;

}

while(1)

{

if(top1==-1 || top2==n)

break;

element1=stack[top1];

element=stack[top2];

if(element>element1)

{

printf("1 ");

top1=top1-1;

}

else

{

if(element<element1)

{

printf("2 ");

top2=top2+1;

}

else

{

printf("0 ");

top2=top2+1;

top1=top1-1;

}

}

}

return 0;

}