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