Tí đang học lập trình Scratch và cậu ta rất thích thú khi viết được các trò chơi theo ý của mình. Hôm nay, Tí đang viết trò chơi Cá lớn ăn cá bé với ý tưởng như sau: Trên màn hình trò chơi xuất hiện \(n\) con cá, các con cá được đánh số từ 1 đến \(n\), con cá thứ \(i\) có kích thước là \(a_i\). Một con cá có kích thước lớn hơn có thể ăn thịt con có kích thước nhỏ hơn, quá trình này được lặp lại cho đến khi trên màn hình chỉ còn 1 con cá thì trò chơi kết thúc. Nếu con cá \(i\) ăn thịt được con cá \(j\) thì con cá \(i\) sẽ có kích thước mới là \(a_i + a_j\).

Trong lúc Tí đang triển khai ý tưởng của mình, Tí tự hỏi với mỗi con cá trên màn hình liệu nó có thể là con sống sót đến cuối cùng không?

Yêu cầu: Em được cho biết kích thước của \(n\) con cá. Hãy giúp Tí xác định xem với mỗi con cá, có tồn tại trường hợp mà nó có thể trở thành con cá sống sót cuối cùng khi trò chơi kết thúc hay không?

Input

• Dòng 1: Chứa số nguyên dương \(n\) là số lượng con cá trên màn hình \((1 ≤ n ≤ 5*10^5).\)

• Dòng 2: Chứa \(n\) số nguyên dương \(a_1, a_2, …, a_n\). Số thứ \(i (i = 1..n)\) là \(a_i\) là kích thước của con con cá thứ \(i (1 ≤ a\)i ≤ 10^9).~

Kết quả:

• Dòng 1: Chứa một dãy \(n\) chữ số \(0\) hoặc \(1\) không chứa dấu cách. Số ở vị trí thứ \(i\) là 1 nếu con cá thứ \(i\) có thể là con sống sót đến cuối cùng, ngược lại là 0.

Ràng buộc

• Subtask 1: 60% test với \( n ≤ 10^3\)

• Subtask 2: 40% test không có ràng buộc gì thêm

Sample Input

4
3 2 8 4

Sample Output

1011

Giải thích

• Con cá 1 có thể ăn các con cá theo thứ tự: cá 2 (tăng kích thước lên 5), sau đó ăn con cá 4 (tăng kích thước lên 9) và cuối cùng ăn con cá 3, lúc này nó là con cá cuối cùng.

• Con cá 2 không thể sống đến cuối cùng

• Con cá 3 có thể ăn các con cá 1, 2, 4 nên nó là con sống đến cuối cùng.

• Con cá 4 có thể sống đến cuối cùng nếu nó ăn các con cá theo thứ tự 1, 2, 3(hoặc 2,1,3).