#include <bits/stdc++.h>
#include "nonintersecting.h"
#include <vector>

using namespace std;
using pii = pair<int, int>;

using nagai = long long;

const int N = 100000;
int mx[2 * N];

int oo = 1e9;

int getmx(int l, int r)
{
    l += N;
    r += N;
    int ans = -1;
    while (l < r)
    {
        if (l & 1)
            ans = max(ans, mx[l++]);
        if (r & 1)
            ans = max(ans, mx[--r]);
        l /= 2, r /= 2;
    }
    return ans;
}

void mod(int x, int y)
{
    x += N;
    mx[x] = y;
    while (x)
    {
        mx[x >> 1] = max(mx[x], mx[x ^ 1]);
        x /= 2;
    }
}

void init()
{
    fill(mx, mx + 2 * N, -1);
}

int n;

vector<int> findlds(vector<int>& a, vector<bool>& del)
{
    init();
    vector<int> dp(n, -1);
    for (int i = 0; i < n; ++i)
    {
        if (del[i])
            continue;
        dp[i] = max(1, getmx(a[i] + 1, n) + 1);
        mod(a[i], dp[i]);
    }
    vector<int> ans;
    int curdp = *max_element(dp.begin(), dp.end());
    if (curdp < 0)
        return {};
    int last = -1;
    for (int i = n - 1; i >= 0; --i)
    {
        if (dp[i] == curdp && a[i] > last)
            last = a[i], --curdp, ans.push_back(i);
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

struct gener
{
    vector<int> dp1;
    vector<vector<int>> mem;
    vector<int> a;
    int lis;
    gener(vector<int>& a)
        : a(a)
    {
        init();
        dp1.resize(n);
        for (int i = n - 1; i >= 0; --i)
        {
            dp1[i] = max(1, getmx(a[i] + 1, n) + 1);
            mod(a[i], dp1[i]);
        }
        lis = *max_element(dp1.begin(), dp1.end());
        mem.resize(n + 1);
        for (int i = 0; i < n; ++i)
            mem[dp1[i]].push_back(i);
    }
    vector<int> gen()
    {
        vector<int> curkek;
        int lastind = -1;
        int lastmem = -1;
        for (int i = 0; i < lis; ++i)
        {
            vector<int> lst;
            for (int x : mem[lis - i])
                if (x > lastind && a[x] > lastmem)
                    lst.push_back(x);
            int x = lst[rand() % lst.size()];
            curkek.push_back(x);
            lastind = x;
            lastmem = a[x];
        }
        return curkek;
    }
};

nagai myt()
{
    return clock() * 1000 / CLOCKS_PER_SEC;
}


pair<std::vector<int>, std::vector<int>> nonintersecting(const std::vector<int> &P) {
    vector<int> a = P;
    n = a.size();
    for (int& x : a)
        --x;
    pair<vector<int>, vector<int>> ans;
    vector<bool> del(n);
    auto mark = [&](vector<int>& kek, bool rev)
    {
        fill(del.begin(), del.end(), 0);
        for (int x : kek)
        {
            if (rev)
                x = n - x - 1;
            del[x] = true;
        }
    };
    gener g1(a);
    auto a1 = a;
    reverse(a1.begin(), a1.end());
    gener g2(a1);
    int abc = g1.gen().size();
    int def = g2.gen().size();
    while (true)
    {
        auto x = g1.gen();
        mark(x, false);
        auto lds = findlds(a, del);
        if (lds.size() == def)
        {
            ans = {x, lds};
            break;
        }
        x = g2.gen();
        reverse(x.begin(), x.end());
        for (auto& y : x)
            y = n - y - 1;
        mark(x, true);
        auto lis = findlds(a1, del);
        if (lis.size() == abc)
        {
            for (auto& x : lis)
                x = n - x - 1;
            reverse(lis.begin(), lis.end());
            ans = {lis, x};
            break;
        }
        if (myt() > 2950)
            break;
    }
    for (auto& x : ans.first)
        ++x;
    for (auto& x : ans.second)
        ++x;
    return ans;
}