사과 상자 분배

테라와 루루는 수확한 사과를 상자에 담아 손님들에게 나누어 주려고 한다.

사과 상자 $N$개가 일렬로 놓여 있다. 상자의 번호는 왼쪽부터 $1,2,\ldots,N$이며 $i$번 상자에는 $A_i$개의 사과가 들어 있다. 모든 상자에 들어 있는 사과의 개수는 서로 다르며, $N$은 홀수이다.

테라와 루루는 손님 한 명에게 다음과 같은 방법으로 두 상자를 나누어 줄 수 있다.

1. 아직 남아 있는 상자 하나와 왼쪽 또는 오른쪽 방향을 고른다.
2. 선택한 방향에 있는 남은 상자들을 가까운 것부터 차례대로 살펴본다.
3. 처음으로 만나는, 선택한 상자보다 사과가 적게 들어 있는 상자를 찾는다.
4. 그러한 상자가 존재한다면 선택한 두 상자를 모두 손님에게 나누어 준다. 존재하지 않는다면 이 선택은 할 수 없다.

손님에게 나누어 준 상자는 줄에서 제거된다. 이후에는 제거된 상자의 자리를 건너뛰고, 남아 있는 상자들의 상대적인 순서만을 고려한다.

테라와 루루는 이 과정을 반복하여 마지막에 상자 하나만 남기고, 남은 상자를 둘이 가지려고 한다.

처음에 $i$번째 위치에 있던 상자가 마지막까지 남을 수 있는지를 모든 $i$에 대해 판별하여라.

첫째 줄에 사과 상자의 개수인 홀수 $N$이 주어진다. ($1\le N\le 500\,000$)

둘째 줄에 각 상자에 들어 있는 사과의 개수 $A_1,A_2,\ldots,A_N$이 공백으로 구분되어 주어진다. () 모든 는 서로 다르다.

$N$개의 정수를 공백으로 구분하여 출력한다.

처음에 $i$번째 위치에 있던 상자가 마지막까지 남을 수 있다면 $i$번째 정수로 1을, 그렇지 않다면 0을 출력한다.