#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int& u : a) cin >> u, --u;
vector<int> where(n);
for (int i = 0; i < n; i++) where[a[i]] = i;
vector<int> b = a;
for (int& u : b) u = -u;
vector<int> lis, pre(n, -1), dp(n);
lis.reserve(n);
for (int u : b) {
int j = lower_bound(lis.begin(), lis.end(), u) - lis.begin();
if (j == (int)lis.size()) lis.push_back(u);
else lis[j] = u;
dp[-u] = j + 1;
if (j > 0) pre[-u] = -lis[j - 1];
}
int z = max_element(dp.begin(), dp.end()) - dp.begin();
lis = vector<int>();
lis.reserve(n);
lis.push_back(z);
while (pre[lis.back()] != -1) {
lis.push_back(pre[lis.back()]);
}
reverse(lis.begin(), lis.end());
vector<int> color(n);
vector<int> next_g(n, n), prev_s(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.back()] < a[i]) {
next_g[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
st = vector<int>();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && a[st.back()] > a[i]) {
prev_s[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
for (int k = 0; k < (int)lis.size(); k++) {
int u = lis[k];
int j = where[u];
color[j] = k + 1;
while (prev_s[j] != -1) {
j = prev_s[j];
if (!color[j])
color[j] = k + 1;
}
j = where[u];
while (next_g[j] < n) {
j = next_g[j];
if (!color[j])
color[j] = k + 1;
}
}
for (int u : color) cout << u << " ";
cout << "\n";
for (int i = 0; i < n; i++) cout << color[where[i]] << " ";
cout << "\n";
}
