#include <iostream>
#include <vector>

int BinarySearch(std::vector<int> &v, int l, int r, int key) {
    while (r-l > 1) {
        int m = l + (r-l)/2;
        if (v[m] >= key) {
            std::cout << v[m] << " ";
            r = m;
        } else {
            std::cout << v[m] << " ";
            l = m;
        }
    }

    return r;
}

void  LongestIncreasingSequence(std::vector<int> &test) {
    if (test.size() == 0)
        return;
    for (int i = 0; i < test.size(); i++)
        std::cout << test[i] << " ";
    std::cout << "\n";

    std::vector<int> gosho(test.size(), 0);
    int length = 1; // always points empty slot in tail

    gosho[0] = test[0];
    for (size_t i = 1; i < test.size(); i++) {
        if (test[i] < gosho[0])
            gosho[0] = test[i];
        else if (test[i] > gosho[length-1])
            gosho[length++] = test[i];
        else {
            gosho[BinarySearch(gosho, -1, length, test[i])] = test[i];
            std::cout << "\n tail = ";
            for (int i = 0; i < length; i++)
                std::cout << gosho[i] << " ";
            std::cout << "\n";
        }
    }
    std::cout << "\n";
    for (int i = 0; i < length; i++)
        std::cout << gosho[i] << " ";
}

int main() {
    std::vector<int> test{ 11, 12, 13, 3, 14, 4, 15, 5, 6, 7, 8, 7, 16, 9, 8 };
    LongestIncreasingSequence(test);
}