Ұзындығы \(n\) болатын қатар берілген — \((p_1,p_2,\dots,p_n)\) тізбегі, онда барлық сандар \(1\)-ден \(n\)-ге дейін қайталанбай орналасқан.

Элемент \(p_i\) инверсияға қатысады деп саналады, егер осындай индекс \(j \neq i\) табылып, келесі шарт орындалса: \(1 \le \min(i,j) < \max(i,j) \le n\) және \(p_{\min(i,j)} > p_{\max(i,j)}.\)

Әр \(1\)-ден \(n\)-ға дейінгі \(i\) үшін анықтаңыз: элемент \(p_i\) кем дегенде бір инверсияға қатыса ма.

Енгізу

Бірінші жолда бүтін сан \(n\) (\(1 \le n \le 3\cdot10^5\)) беріледі. Екінші жолда \(n\) бүтін сан: \(p_1, p_2, \dots, p_n\) — қатар.

Шығару

\(n\) бүтін санды шығарыңыз: әр \(i\) үшін \(1\), егер элемент \(p_i\) кем дегенде бір инверсияға қатысса, немесе \(0\), егер қатыспаса.

Мысалдар

Енгізу 1

5
1 2 3 5 4

Жауап 1

0 0 0 1 1

Ескертпелер

Жалғыз инверсия (5,4) жұбы.