bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
class FastIO {
public:
    int read() {
        int o = 1, x; char ch;
        while (!isdigit(ch = getchar())) {
            if (ch == '-') {
                o = -1;
            }
        }
        x = ch ^ 48;
        while (isdigit(ch = getchar())) {
            x = (x << 3) + (x << 1) + (ch ^ 48);
        }
        return o * x;
    }
} ; FastIO io;

void calcqwq();
const int N = 500100, inf = 1e18;
inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }
int a[N], f[N], g[N], n, tr[N];
void add(int x, int v) { for (; x < N; x += (x &- x)) tr[x] = max(tr[x], v); }
int query(int x) { int s = 0; for (; x; x -= (x &- x)) s = max(s, tr[x]); return s; }
int query(int l, int r) { return query(r) - query(l - 1); }
struct qwq { int x, id; } b[N];
signed main() {
    atexit(calcqwq);
    n = io.read();
    for (int i = 1; i <= n; ++i) a[i] = io.read(), b[i].x = a[i], b[i].id = i;
    sort(b + 1, b + n + 1, [&](auto l, auto r) { return l.x < r.x; });
    int idx = 1; map<int, int> mp;
    for (int i = 1; i <= n; ++i) if (b[i].x != b[i - 1].x || i == 1) {
        if (b[i].x - b[i - 1].x == 1 || i == 1) mp[b[i].x] = ++idx;
        else mp[b[i].x] = (idx += 2);
    } idx++;
    for (int i = 1; i <= n; ++i) a[i] = mp[a[i]];
    for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << '\n';
    for (int i = 1; i <= n; ++i) {
        f[i] = query(a[i] - 1) + 1;
        add(a[i], f[i]);
    } memset(tr, 0, sizeof tr);
    for (int i = n; i; i--) {
        g[i] = query(a[i] + 1, N - 1) + 1;
        add(a[i], g[i]);
    } memset(tr, 0, sizeof tr);
    for (int i = 1; i <= n; ++i) cout << f[i] << ' '; cout << '\n';
    for (int i = 1; i <= n; ++i) cout << g[i] << ' '; cout << '\n';
    int mx = 0;
    for (int i = 3; i <= n; ++i) {
        add(a[i - 2], f[i]);
        mx = max(mx, g[i] + query(a[i] - 2) + 1);
    } cout << mx << '\n';
    return 0;
}
bool endmem;
void calcqwq() {
    fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}

菜到了一定程度啥也不会的小萌新求看一下 $g$ 数组哪里求错了，瞪了一个小时了/kk，真的不会写代码了/ll