#include <vector>
#include <cstdint>


namespace cg
  {
    using ui_m_t = std::uintmax_t;
    template<typename t>
    using vec = std::vector<t>;
    typedef vec<ui_m_t> vuimt;
    vuimt lung_incre_subsqn (const vec<std::uintmax_t> seq)
      {
        // stole an algorithm from wikipedia
        vuimt C;
        vuimt M;
        M.push_back(UINTMAX_MAX);
        ui_m_t Z = 0;
        for (ui_m_t Y = 0; Y < seq.size (); Y++)
          {
            ui_m_t l = 1, h = Z + 1, N;
            while (l < h)
              {
                ui_m_t m = l + ((h - l) / 2);
                if (seq.at(M.at(m)) >= seq.at(Y))
                  {
                    h = m;
                  } // if (seq.at(M.at(m)) >= seq.at(Y))
                else
                  {
                    l = m + 1;
                  } // else
              } // while (l < h)
            N = l;
            C.push_back(M.at(N - 1));
            if (N >= M.size())
              {
                M.push_back(Y);
              } // if (N >= M.size())
            else
              {
                M[N] = Y;
              } // else
            if (N > Z)
              {
                Z = N;
              } // if (N > Z)
          } // for (ui_m_t Y = 0; Y < seq.size (); Y++)
        std::vector<std::uintmax_t> H = vuimt( Z, 0 );
        ui_m_t f = M.at(Z);
        for (ui_m_t q = Z - 1; q < UINTMAX_MAX; q--)
          {
            H[q] = seq.at(f);
            f = C.at(f);
          } // for (ui_m_t q = Z - 1; q <= 0; q--)
        return H;
      } // vuimt lung_incre_subsqn (const vec<std::uintmax_t> seq)
  } // namespace cg