Bạn được cho một dãy input gồm \(n\) số. Mỗi số nguyên từ \(1\) đến \(n\) xuất hiện đúng một lần trong dãy.

Nhiệm vụ của bạn là tạo một dãy output đã sắp xếp sử dụng hai ngăn xếp (stack). Ở mỗi bước, bạn có thể thực hiện một trong các thao tác sau:

• Di chuyển số đầu tiên từ dãy input vào một stack
• Di chuyển một số từ một stack đến cuối dãy output

Input

Dòng đầu tiên là một số nguyên \(n\).

Dòng thứ hai chứa \(n\) số nguyên: các số của dãy input.

Output

In ra \(n\) số nguyên: với mỗi số là stack nó được chuyển vào (\(1\) hoặc \(2\)).

Bạn có thể in ra bất kỳ đáp án hợp lệ nào. Nếu không có đáp án, in ra IMPOSSIBLE.

Giới hạn

• \(1 \le n \le 2 \cdot 10^5\)

Ví dụ

Input

5
2 3 1 5 4

Output

1 2 1 1 2