Using some sequence \(1 \leq x_1<y_1<x_2<y_2<\cdots<x_k<y_k \leq N\), the solution can be represented as follows.

• Exchange gold for silver on Day \(x_1\) and exchange silver for gold on Day \(y_1\), multiplying the amount of gold by \(A_{x_1}/A_{y_1}\).
• Exchange gold for silver on Day \(x_2\) and exchange silver for gold on Day \(y_2\), multiplying the amount of gold by \(A_{x_2}/A_{y_2}\).
• \(\vdots\)
• Exchange gold for silver on Day \(x_k\) and exchange silver for gold on Day \(y_k\), multiplying the amount of gold by \(A_{x_k}/A_{y_k}\).

Incidentally, allowing multiple trades on a single day does not change the final amount of gold. (Making two trades on a day is the same as making no trades.) Thus, “exchanging gold for silver on Day \(x_i\) and exchanging silver for gold on Day \(y_i\), multiplying the amount of gold by \(A_{x_i}/A_{y_i}\)” is equivalent to:

• exchanging gold for silver on Day \(x_i\) and exchanging silver for gold on Day \(x_i+1\), multiplying the amount of gold by \(A_{x_i}/A_{x_i+1}\),
• exchanging gold for silver on Day \(x_i+1\) and exchanging silver for gold on Day \(x_i+2\), multiplying the amount of gold by \(A_{x_i+1}/A_{x_i+2}\),
• \(\vdots\)
• exchanging gold for silver on Day \(y_i-1\) and exchanging silver for gold on Day \(y_i\), multiplying the amount of gold by \(A_{y_i-1}/A_{y_i}\).

To sum up, deciding when to trade is equivalent to deciding whether to “exchange gold for silver on Day \(i\) and exchange silver for gold on Day \(i+1\), multiplying the amount of gold by \(A_{i}/A_{i+1}\)” for each \(1 \leq i \leq N-1\).

Obviously, it is optimal to do this operation only for those \(i\) such that \(A_i > A_{i+1}\). This allows us to write the following code:

n=int(input())
a=list(map(int,input().split()))

ans=[0]*n

for i in range(n-1):
	if a[i]>a[i+1]:
		ans[i]^=1
		ans[i+1]^=1

print(*ans)

The complexity is \(O(N)\).