bear-and-bowling-2

View Russian Translation

Limak is an old brown bear.
He often goes bowling with his friends.
You may know that usually the aim is to roll a ball and hit as many pins as possible.
But today they decided to play with slightly different rules.

There are N pins in a row, numbered 1 through N.
They are evenly distributed and a rolled ball of size k always hits k consecutive pins.

Each pin has a number written on it, denoting its value.
i-th pin has value A[i].

The main rule today is that one can't hit a pin with value lower than some pin which isn't hit.
It turns out that for some balls it could be impossible!

Limak is one of the best bowlers among bears.
Though it will mean nothing if he picks a wrong ball.
You don't want him to be sad, do you?

Help Limak and for each size of ball check if he can use that ball without breaking a rule described above.
For each size you should print 1 or 0, without any spaces.

Input format:

The first line contains one integer number N, denoting number of pins.
The second line contains N space-separated integers A[1], A[2], ..., A[N], denoting values of pins.

Output format:

In the single line print one string with N characters.
i-th character should be 1 if Limak can use a ball of size i, and 0 otherwise.

Constraints:

1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^9

SAMPLE INPUT
7
4 6 6 6 3 6 1

SAMPLE OUTPUT
1110011

Explanation

With a ball of size 1 or 2 or 3 Limak can try to hit pins with values 6 only.
There is no way to use balls of sizes 4 and 5.
With size 6 Limak can hit all pins except the last one which has value not greater than any other pin.
Finally, he can hit all pins with size 7.

Source: hackerearth | Difficulty: MEDIUM
Tags: Greedy algorithms


Solutions: