Lexicographicaly Longest Increasing Subsequence

struct node
{
    int val, parent;

    node() {}

    node(int val, int parent)
    {
        this -> val = val;
        this -> parent = parent;
    }
};

int pos(std::vector<std::vector<node> > &tail, unsigned int lhs, unsigned int rhs, int key)
{
    while(rhs - 1 > lhs)
    {
        int mid = lhs + (rhs - lhs) / 2;
        tail[mid].back().val >= key ? rhs = mid : lhs = mid;
    }

    if(rhs == tail.size() - 1)
    {
        tail.push_back(std::vector<node>(1, node(INF, 0)));
        tail[tail.size() - 2].resize(0);
    }

    return rhs;
}

std::vector<int> LexMinLIS(std::vector<int> &seq)
{
    std::vector<int> LexMin;
    std::vector<std::vector<node> > tail(3);
    tail[0].push_back(node(-INF, -1)), tail[1].push_back(node(seq[0], 0)), tail[2].push_back(node(INF, 0));

    for(unsigned int i = 1; i < seq.size(); i++)
    {
        int p = pos(tail, 0, tail.size(), seq[i]);
        tail[p].push_back(node(seq[i], tail[p - 1].size() - 1));
    }

    node c = tail[tail.size() - 2].back();

    for(unsigned int i = tail.size() - 2; i > 0; i--)
    {
        LexMin.push_back(c.val);
        c = tail[i - 1][c.parent];
    }

    return LexMin;
}