require "table2"

local function longest_increasing_subsequence(x)
    local n = #x
    if n == 0 then return {} end
    if n == 1 then return x end
    local p = table.rep(n, 0)
    local m = table.rep(n, 0)
    local len = 0
    for i = 1, n do
        local lo = 1
        local hi = len
        while lo <= hi do
            local mid = math.ceil((lo + hi) / 2)
            if x[m[mid]] < x[i] then
                lo = mid + 1
            else
                hi = mid - 1
            end
        end
        if lo > 1 then p[i] = m[lo - 1] end
        m[lo] = i
        if lo > len then len = lo end
    end
    local res = table.rep(len, 0)
    if len > 0 then
        local k = m[len]
        for i = len, 1, -1 do
            res[i] = x[k]
            k = p[k]
        end
    end
    return res
end

local lists = {
    {3, 2, 6, 4, 5, 1},
    {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
}

lists:foreach(|l| -> do
    print(longest_increasing_subsequence(l):concat(", "))
end)