In the multiplayer game Agar.io, players control bacteria. Each bacterium has size — a positive integer. If two bacteria of different sizes meet, the larger bacterium engulfs the smaller bacterium. In this case, the smaller bacterium disappears, and the size of the larger bacterium increases by the size of the smaller bacterium. If two bacteria of the same size meet, nothing happens. The winner is the player whose bacterium remains on the game
field one.
There are n players in the game, you are given the sizes of their bacteria. Determine which of the players have the opportunity to win in this game.
Input data format
The program receives an integer n, 1 ≤ n≤ 10
5 — number of players. The next n lines contain one number each a
i — bacteria sizes, 1 ≤ a
i ≤ 10
9. The numbers a
i are in non-decreasing order.
Output data format
The program should output n numbers equal to "0" or "1", one number per line. If the i-th number is equal to 0, then this means that the i-th player (whose bacterium size was originally
a
i) cannot under any circumstances win this game. If the i-th number is equal to 1, then this means that the i-th player has the opportunity to win in this game.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
1
1
3
4 |
0
0
1
1 |
In the example from condition 4, bacteria of size 1, 1, 3, 4. Bacteria of size 1 can't do anything
eat, so they can't win. A size 4 bacterium can eat everyone. Bacteria size 3
can eat two bacteria in turn of size 1. Then her size will become 5, after that she can
eat bacteria size 4 and win. Answer: 0, 0, 1, 1. |