Placing Medals on a Binary Tree

You have a chart of a perfect binary tree, like the one in Figure 1. The chart shows a finite part of the tree, but you can attach more nodes below the leaves and make the tree as deep as you need.

Figure 1. A chart of a perfect binary tree

Every node has a depth, defined recursively. The root has depth 0, and both children of a node of depth $d$ have depth $d + 1$.

You also have a pile of medals, each engraved with a number. You want to know whether the medals can be placed on the chart under all of the following conditions.

• A medal engraved with $d$ goes on a node of depth $d$.
• Each node holds at most one medal.
• The path from a node holding a medal up to the root passes through no other node holding a medal.

You place the medals one at a time, from the top of the pile down to the bottom. When no placement of the current medal satisfies the conditions, you throw that medal away and move on to the next one.

A medal can sometimes go on several different nodes, and you want the best placement. Between two placements that satisfy the conditions, the one that places a medal nearer the top of the pile is better. For example, with four medals, a placement that keeps only the first and the second medal is better than one that keeps the first, the third and the fourth.

Consider a pile of six medals engraved with 2, 3, 1, 1, 4 and 2, from top to bottom.

• The first medal, engraved with 2, can be placed as in Figure 2 (A).
• The second medal, engraved with 3, can be placed as in Figure 2 (B).
• The third medal, engraved with 1, cannot be placed while the second medal stays where Figure 2 (B) puts it, because both nodes of depth 1 lie on a path from a node that already holds a medal up to the root. Moving the second medal to another node that satisfies the conditions gives the placement in Figure 2 (C).
• The fourth medal, again engraved with 1, cannot be placed however the three medals already on the chart are rearranged, so it is thrown away.
• The fifth medal, engraved with 4, can be placed as in Figure 2 (D).
• The last medal, engraved with 2, fits on no node under any rearrangement.

Figure 2. Medal placements

The input is a single test case in the format below.

n
x1
.
.
.
xn

The first line has the number of medals $n$ ($1 \le n \le 5 \times 10^5$). Each of the next $n$ lines has one positive integer. The $i$-th of them, $x_i$ ($1 \le x_i \le 10^9$), is engraved on the $i$-th medal from the top of the pile.

Choose the best placement. For each $i$ from 1 through $n$, print Yes on its own line if the $i$-th medal is placed, and No otherwise.