#include<bits/stdc++.h> #define ll long long #define ld long double #define vl vector<ll> #define vi vector<int> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define sz(v) (ll)(v.size()) #define f first #define s second #define pii pair<int, int> #define pll pair<ll, ll> using namespace std; const ll sz = 2e5+5; ll a[sz], segtree[4*sz]; void build(ll v, ll l, ll r) { if(l == r) segtree[v] = a[l]; else { ll mid = (l + r) / 2; build(2*v, l, mid); build(2*v+1, mid+1, r); segtree[v] = max(segtree[2*v], segtree[2*v+1]); } } void update(ll v, ll l, ll r, ll idx) { if(l == r) segtree[v] = 0; else { ll mid = (l + r) / 2; if(idx <= mid) update(2*v, l, mid, idx); else update(2*v+1, mid+1, r, idx); segtree[v] = max(segtree[2*v], segtree[2*v+1]); } } ll findres(ll v, ll l, ll r, ll tl, ll tr) { if(tl > tr) return 0; if(l == tl && r == tr) return segtree[v]; ll mid = (l + r) / 2; ll lans = findres(2*v, l, mid, tl, min(mid, tr)); ll rans = findres(2*v+1, mid+1, r, max(mid+1, tl), tr); return max(lans, rans); } void solve() { ll n, x, i, j; cin >> n >> x; ll t[n+1]; for(i = 1; i <= n; i++) cin >> t[i]; ll m[n+1], r[n+1]; vl vect; m[0] = 0; m[1] = 1; vect.pb(t[1]); for(i = 2; i <= n; i++) { if(t[i] > vect.back()) vect.pb(t[i]); else { ll o = lower_bound(all(vect), t[i]) - vect.begin(); vect[o] = t[i]; } m[i] = lower_bound(all(vect), t[i]) - vect.begin() + 1; } vl v; v.pb(t[n]); r[n] = 1; for(i = n - 1; i >= 1; i--) { if(t[i] < v.back()) { r[i] = sz(v) + 1; v.pb(t[i]); } else { ll l = 0, tr = sz(v) - 1, bst = sz(v); while(l <= tr) { ll mid = (l + tr) / 2; if(v[mid] > t[i]) l = mid + 1; else { bst = mid; tr = mid - 1; } } v[bst] = t[i]; r[i] = bst + 1; } } for(i = 1; i <= n; i++) cout << m[i] << ' '; cout << "\n"; for(i = 1; i <= n; i++) cout << r[i] << ' '; cout << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll tests = 1; //cin >> tests; while(tests--) { solve(); } }