// -----------------------------------------------------------------------------
// Longest Increasing Subsequence                                            C++
// -----------------------------------------------------------------------------
std::vector<int> LIS(std::vector<int> &a)
{
    int n = a.size();
    std::vector<int> prev(n);
    std::vector<int> tail(n + 1);
    int length = 0;
    for (int i = 0; i < n; i++) {
        int low = 1;
        int high = length;
        while (low <= high) {
            int mid = (low + high + 1) / 2;
            if (a[tail[mid]] < a[i])
                low = mid + 1;
            else
                high = mid - 1;
        }
        int pos = low;
        prev[i] = tail[pos - 1];
        tail[pos] = i;
        if (pos > length) length = pos;
    }
    std::vector<int> lis(length);
    int k = tail[length];
    for (int j = length - 1; j >= 0; j--) {
        lis[j] = a[k];
        k = prev[k];
    }
    return lis;
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// Longest Increasing Subsequence                                             C#
// -----------------------------------------------------------------------------
static int[] LIS(int[] a)
{
    int n = a.Length;
    int[] prev = new int[n];
    int[] tail = new int[n + 1];
    int length = 0;
    for (int i = 0; i < n; i++) {
        int low = 1;
        int high = length;
        while (low <= high) {
            int mid = (low + high + 1) / 2;
            if (a[tail[mid]] < a[i])
                low = mid + 1;
            else
                high = mid - 1;
        }
        int pos = low;
        prev[i] = tail[pos - 1];
        tail[pos] = i;
        if (pos > length) length = pos;
    }
    int[] lis = new int[length];
    int k = tail[length];
    for (int j = length - 1; j >= 0; j--) {
        lis[j] = a[k];
        k = prev[k];
    }
    return lis;
}
// -----------------------------------------------------------------------------

# ------------------------------------------------------------------------------
# Longest Increasing Subsequence                                          Python
# ------------------------------------------------------------------------------
def LIS(a):
    n = len(a)
    prev = [0] * n
    tail = [0] * (n + 1)
    length = 0
    for i in range(n):
        low = 1
        high = length
        while low <= high:
            mid = (low + high + 1) // 2
            if a[tail[mid]] < a[i]:
                low = mid + 1
            else:
                high = mid - 1
        pos = low
        prev[i] = tail[pos - 1]
        tail[pos] = i
        if pos > length:
            length = pos
    lis = [0] * length
    k = tail[length]
    for i in range(length)[::-1]:
        lis[i] = a[k]
        k = prev[k]
    return lis
# ------------------------------------------------------------------------------