All Tracks Data Structures Stacks Basics of Stacks Problem

Fun Game <Capillary>
/

Data Structures, Queue, Stacks

Problem
Editorial
Analytics

\(A\) 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 numbers \; in \; the \; list \le 10^9$$

 

SAMPLE INPUT
3
1 2 3
SAMPLE OUTPUT
2 2 0
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]

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?