Phân loại chỉ số theo LIS

Cho dãy $a$ gồm $n$ phần tử $a_1,a_2,\dots ,a_n$.

Một dãy con $a_{i_1},a_{i_2},\dots ,a_{i_k}$ với $1\le i_1<i_2<\dots <i_k\le n$ được gọi là tăng nếu $a_{i_1}<a_{i_2}<\dots <a_{i_k}$. Một dãy con tăng được gọi là dài nhất nếu nó có độ dài lớn nhất trong tất cả các dãy con tăng của $a$ (viết tắt: LIS).

Một dãy có thể có nhiều LIS khác nhau. Hãy phân loại mọi chỉ số $i$ ($1\le i\le n$) vào ba nhóm:

1. Nhóm gồm các chỉ số $i$ mà $a_i$ không thuộc bất kỳ LIS nào.
2. Nhóm gồm các chỉ số $i$ mà $a_i$ thuộc ít nhất một nhưng không phải tất cả các LIS.
3. Nhóm gồm các chỉ số $i$ mà $a_i$ thuộc tất cả các LIS.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: số phần tử của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một xâu gồm $n$ ký tự. Ký tự thứ $i$ là '1', '2' hoặc '3' tương ứng với nhóm mà chỉ số $i$ thuộc về.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^5$

Ví dụ