function longest_increasing_subsequence(v::Vector{Int})::Vector{Int}
    M = zeros(Int, length(v)) # M[L] stores last index of sequence with length L.
    P = zeros(Int, length(v)) # P[i] stores predecessor of element i in longest sequence.
    Longest = 0
    for i = eachindex(v)
        # Binary search for position in longest-sequence-so-far
        lo, hi = 1, Longest+1
        while lo < hi
            mid = round(Int, floor((lo+hi)/2))
            if v[i] < v[M[mid]]
                hi = mid
            else
                lo = mid+1
            end
        end
        @assert lo == hi
        # Update predecessor of current index.
        P[i] = lo > 1 ? M[lo-1] : -1
        M[lo] = i

        if lo >= Longest
            Longest = lo
        end
    end

    # Reconstruct sequence.
    seq = zeros(Int, Longest)
    i = M[Longest]
    for j = Longest:-1:1
        seq[j] = v[i]
        i = P[i]
    end
    seq
end

function sort_by_length!(v::Vector{Vector{T}}) where {T}
    sort!(v; rev=true, by=length)
end

function liss2(v::AbstractArray{T}, st::Vector{Vector{T}}=Vector{T}[])::Vector where {T}
    init = isempty(st)
    if length(v) <= 1
        push!(st, collect(v))
    elseif length(v) == 2
        if v[1] < v[2]
            push!(st, collect(v))
        else
            push!(st, [v[1]], [v[2]])
        end
    else
        liss2((@view v[begin+1:end]), st)
        sort_by_length!(st)
        for s = st
            if v[begin] < s[begin]
                push!(st, vcat(v[begin], s))
            end
        end
        push!(st, [v[begin]])
    end
    if init
        sort_by_length!(st)
    end
    st
end

function liss3(v::AbstractArray{T}) where {T}
    L = zeros(Int, length(v))
    prevs = zeros(Int, length(v))

    findprevel(val, i) = findlast(e -> e > 0 && v[e] < val, (@view L[begin:i]))
    longest = 0
    for i = eachindex(v)
        p = findprevel(v[i], i)
        if isnothing(p)
            L[1] = i
        else
            prevs[i] = L[p]
            L[p+1] = i
            longest = max(longest, p+1)
        end
    end

    # Reconstruct
    vs = zeros(T, longest)
    e = L[longest]
    for i = longest:-1:1
        vs[i] = v[e]
        e = prevs[e]
    end
    vs
end