/**********长度和以a[i]为结尾的LIS的个数************/  
#include <bits/stdc++.h> 
  
using namespace std;  
typedef long long LL;  
const int mod = 998244353;  
const int maxn = 5e5+55;  
struct node  
{  
    LL len,num;  
} tr[maxn];  
int n,m,a[maxn],c[maxn];  
node pre[maxn],cur[maxn];  
inline int lowbit(int x)  
{  
    return x&(-x);  
}  
void add(int x,node e)  
{  
    while(x <= m)  
    {  
        if(tr[x].len == e.len) tr[x].num = (tr[x].num+e.num)%mod;  
        else if(tr[x].len < e.len)  
        {  
            tr[x].len = e.len;  
            tr[x].num = e.num;  
        }  
        x += lowbit(x);  
    }  
}  
node query(int x)  
{  
    node res = {0,0};  
    while(x > 0)  
    {  
        if(res.len == tr[x].len) res.num = (res.num+tr[x].num)%mod;  
        else if(res.len < tr[x].len)  
        {  
            res.len = tr[x].len;  
            res.num = tr[x].num;  
        }  
        x -= lowbit(x);  
    }  
    return res;  
}  
LL qpow(LL a,LL x)  
{  
    LL res = 1;  
    while(x)  
    {  
        if(x&1) res = res * a % mod;  
        a = a * a % mod;  
        x >>= 1;  
    }  
    return res;  
}  
int main()  
{  
    cin >> n;  
    for(int i = 0; i < n; ++i) cin >> a[i],c[i] = a[i];  
    sort(c,c+n);  
    m = unique(c,c+n) - c;  
    for(int i = 0; i < n; ++i) a[i] = lower_bound(c,c+m,a[i])-c+1;  
    for(int i = 0; i < n; ++i)  
    {  
        pre[i] = query(a[i]-1);  
        if(++pre[i].len == 1) pre[i].num = 1;  
        add(a[i],pre[i]);  
    }  
    for(int i=0;i<n;i++)  
    {  
        cout<<pre[i].len<<' ';//长度 
    }  
    cout<<endl;  
    for(int i=0;i<n;i++)  
    {  
        cout<<pre[i].num<<' ';//数量 
    }  
}