考虑一个暴力的做法：
建立一个超级起点 \(a_0 = 0\) 超级终点 \(a_{n + 1} = \inf\)。
求出 \(f_i\) 代表 \(1\sim i\) 且以 \(i\) 结尾的 \(\text{LIS}\) 长度。
考虑 \(f_i = \max\{f_j + 1\}(j < i \land a_j < a_i)\) 这个转移的式子，如果 \(f_i = f_j + 1(j < i\land a_j < a_i)\) 就连一条 \(j\to i\) 的边。
那么从 \(0\to n + 1\) 的一条路径就代表着一个合法的 \(\text{LIS}\)，路径上的点就是可能出现在 \(\text{LIS}\) 中的编号。
那么如果 \(a_i\) 满足任意 \(\text{LIS}\) 都有它，就需要满足对于任意 \(j\not = i\)，\(f_j\not = f_i\) 或不存在经过 \(j\) 的合法路径。
因为每条路径的 \(f_i\) 必然是递增的，同一种 \(f_i\) 不会出现 \(2\) 次，那么就会存在一条经过 \(j\) 而不经过 \(i\) 的路径，\(i\) 就不是唯一的。
考虑到这个做法的主要瓶颈就是处理 \(i\) 是否会在一条 \(0\to n + 1\) 的路径中出现。
那么就可以拆成 \(0\to i\to n + 1\)。
首先能发现通过 \(f_i\) 的转移就一定存在 \(0\to i\) 的路径。
于是就只用考虑是否有 \(i\to n + 1\) 的路径了。
那么考虑相当于建反边转化为从 \(n + 1\to i\) 的路径，从 \(n\) 到 \(1\) 倒着处理。
那么 \(i\) 合法就相当于是存在 \(j > i\) 满足 \(f_j = f_i + 1, a_j > a_i\) 且 \(j\) 合法。
因为最后一个条件首先保证了存在 \(n + 1\to j\) 的路径，前面的条件保证了反图中存在 \(j\to i\) 的边，于是就有 \(n + 1\to i\) 的路径。
能够发现只需要对于 \(f\) 的取值 \(x\) 维护满足 \(f_i = x\) 且 \(i\) 合法的 \(\max\{i\}\)，这是容易做到的而且是线性的。
时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
const int maxn = 1e5 + 10;
int a[maxn], f[maxn], stk[maxn], m;
int mx[maxn], op[maxn], cnt[maxn];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
a[++n] = 2e5;
for (int i = 1; i <= n; i++) {
int l = 0, r = m;
while (l <= r) {
int mid = (l + r) >> 1;
a[i] > a[stk[mid]] ? (f[i] = mid + 1, l = mid + 1) : (r = mid - 1);
}
f[i] > m && (m++), stk[f[i]] = i;
}
mx[m] = 2e5;
for (int i = n - 1; i; i--) op[i] = a[i] < mx[f[i] + 1], op[i] && (mx[f[i]] = std::max(mx[f[i]], a[i]), cnt[f[i]]++);
for (int i = 1; i < n; i++) printf("%d", ! op[i] ? 1 : (cnt[f[i]] > 1 ? 2 : 3));
return 0;
}