function lis(sequence X, integer N = length(X))
    sequence P = repeat(0,N)
    sequence M = repeat(0,N)
    integer len = 0
    for i=1 to N do
        integer lo = 1
        integer hi = len
        while lo<=hi do
            integer mid = ceil((lo+hi)/2)
            if X[M[mid]]<X[i] then
                lo = mid + 1
            else
                hi = mid - 1
            end if
        end while
        if lo>1 then
            P[i] = M[lo-1]
        end if
        M[lo] = i
        if lo>len then len = lo end if
    end for
    sequence res = repeat(0,len)
    if len>0 then
        integer k = M[len]
        for i=len to 1 by -1 do
            res[i] = X[k]
            k = P[k]
        end for
    end if
    return res
end function

constant tests = {{3, 2, 6, 4, 5, 1},
                  {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}}
for i=1 to length(tests) do
    ?lis(tests[i])
end for