K-th LIS

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e5 + 5;
constexpr ll Inf = 2e18;

ll Mul(ll a, ll b)
{
    if (b == 0)
        return 0;

    if (a > Inf / b)
        return Inf;

    return a * b;
}

ll Sum(ll a, ll b)
{
    if (a + b > Inf)
        return Inf;
    return a + b;
}

struct SegmentTree
{
    int n;

    pair<int, ll> st[N * 4];

    SegmentTree()
    {
        fill_n(st, N * 4, make_pair(0, 1));
    }

    pair<int, ll> Combine(const pair<int, ll> &a, const pair<int, ll> &b)
    {
        if (a.first > b.first)
            return a;
        else if (b.first > a.first)
            return b;

        if (a.first == 0)
            return a;

        return make_pair(a.first, Sum(a.second, b.second));
    }

    void Update(int id, int l, int r, const int &x, const pair<int, ll> &v)
    {
        if (l > x || r < x)
            return;
        if (l == x && r == x)
        {
            st[id] = Combine(st[id], v);
            return;
        }

        Update(id << 1, l, (l + r) / 2, x, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);
        st[id] = Combine(st[id << 1], st[id << 1 | 1]);
    }

    void Update(int x, const pair<int, ll> &v)
    {
        Update(1, 1, n, x, v);
    }

    pair<int, ll> Get(int id, int l, int r, const int &a, const int &b)
    {
        if (l > b || r < a)
            return make_pair(0, 1);

        if (l >= a && r <= b)
            return st[id];

        return Combine(Get(id << 1, l, (l + r) / 2, a, b), Get(id << 1 | 1, (l + r) / 2 + 1, r, a, b));
    }

    pair<int, ll> Get(int l, int r)
    {
        return Get(1, 1, n, l, r);
    }
} f;

int n, a[N], b[N];
ll dp[N], rdp[N];
int res[N];
vector<int> x[N];

ll k;

void Read()
{
    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        x[a[i]].emplace_back(i);
    }
}

void Solve()
{
    int ans = 0;

    f.n = n;
    for (int i = n; i; --i)
    {
        pair<int, ll> v = f.Get(a[i] + 1, n);

        dp[i] = v.second;
        b[i] = v.first + 1;
        ans = max(ans, b[i]);

        f.Update(a[i], make_pair(b[i], dp[i]));
    }

    x[0].emplace_back(0);
    rdp[0] = 1;
    b[0] = ans + 1;

    int val = 0;

    for (int i = ans; i; --i)
    {
        ll sum(0);

        for (int j = val + 1; j <= n; ++j)
        {
            int h = 0;
            ll tmp = 0;
            ll tmprdp = 0;

            for (auto t : x[j])
            {
                while (h < (int)x[val].size() && x[val][h] <= t)
                {
                    tmprdp = Sum(tmprdp, rdp[x[val][h]]);
                    ++h;
                }

                if (b[t] == i)
                {
                    rdp[t] = tmprdp;
                    tmp = Sum(tmp, Mul(dp[t], tmprdp));
                }
            }

            if (Sum(sum, tmp) >= k)
            {
                k -= sum;
                res[ans - i + 1] = j;
                val = j;

                goto done;
            }

            sum += tmp;
        }

        cout << -1;
        return;

    done:;
        // cout << k << "\n";
    }

    for (int i = 1; i <= ans; ++i)
        cout << res[i] << " ";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("kthlis.inp", "r"))
    {
        freopen("kthlis.inp", "r", stdin);
        freopen("kthlis.out", "w", stdout);
    }
    Read();
    Solve();
}