Fish Feast

You are given \( n \) fishes. The mass of the \( i\text{-th} \) fish is \( a_i \) grams.

A fish \( x \) can eat another fish \( y \) if and only if \( a_x > a_y \). When \( x \) eats \( y \), fish \( y \) disappears and the mass of fish \( x \) becomes \( a_x + a_y \).

You can specify the order in which the fishes eat each other arbitrarily, until only one fish remains.

Determine for each fish whether it is possible for that fish to be the unique remaining fish at the end. If it is impossible to end up with exactly one fish (i.e. no sequence of moves results in a single fish), then none of the fishes satisfy the condition.

In other words, for each fish \( i \) check whether there exists an eating order such that if we start with fish \( i \) (with initial mass \( a_i \)) and make it eat all the other \( n-1 \) fishes (in some order), at every step the current fish has a mass strictly greater than the fish it needs to eat. A greedy strategy is to eat the fishes in increasing order of mass. Formally, if we sort all other fishes' masses in ascending order as \( b_1, b_2, \ldots, b_{n-1} \), then starting with \( c = a_i \), fish \( i \) can be the final fish if for every \( k=1,2,\ldots,n-1 \) we have \[ c > b_k, \quad \text{and then update} \quad c \leftarrow c+b_k. \] Otherwise, fish \( i \) cannot finish the process. Note that if no fish can eat all the others, then the answer for every fish is false.

inputFormat

The first line contains a single integer \( n \) (\( 1 \le n \le 10^5 \)) — the number of fishes.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) (\( 1 \le a_i \le 10^9 \)) — the masses of the fishes.

outputFormat

Output \( n \) integers separated by spaces. The \( i\text{-th} \) integer should be 1 if it is possible for the \( i\text{-th} \) fish to be the unique remaining fish, or 0 otherwise.

Note: If no sequence of moves can result in a single fish, then output 0 for every fish.

sample

1
100

1