// Subsecuencia creciente más larga: estrictamente creciente, salvo donde se dice otra cosa.
#pragma once

#include <algorithm>
#include <cstddef>
#include <vector>

struct LisTable {
    std::vector<int> ending;  // ending[i]: el largo de la más larga que termina justo en a[i]
    std::vector<int> pred;    // índice del elemento anterior en esa subsecuencia, o -1
};

inline LisTable lis_quadratic(const std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    LisTable t{std::vector<int>(a.size(), 1), std::vector<int>(a.size(), -1)};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && t.ending[j] + 1 > t.ending[i]) {
                t.ending[i] = t.ending[j] + 1;
                t.pred[i] = j;
            }
        }
    }
    return t;
}

inline int lis_length_quadratic(const std::vector<int>& a) {
    const LisTable t = lis_quadratic(a);
    return t.ending.empty() ? 0 : *std::max_element(t.ending.begin(), t.ending.end());
}

// Invariante: tails es estrictamente creciente, y tails[k] es el menor último valor posible de una
// subsecuencia creciente de largo k + 1 entre los elementos ya vistos.
inline std::size_t lis_length_tails(const std::vector<int>& a) {
    std::vector<int> tails;
    for (int x : a) {
        const auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails.size();
}

// Con upper_bound se calcula otra cosa: la más larga que no decrece.
inline std::size_t non_decreasing_length_tails(const std::vector<int>& a) {
    std::vector<int> tails;
    for (int x : a) {
        const auto it = std::upper_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails.size();
}

inline std::vector<int> final_tails(const std::vector<int>& a) {
    std::vector<int> tails;
    for (int x : a) {
        const auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails;
}

// Con reconstrucción: tail_index[k] es el índice de tails[k] en a, y pred[i] se fija cuando entra a[i].
inline std::vector<int> lis_indices(const std::vector<int>& a) {
    std::vector<int> tails;
    std::vector<int> tail_index;
    std::vector<int> pred(a.size(), -1);
    for (int i = 0; i < static_cast<int>(a.size()); i++) {
        const auto it = std::lower_bound(tails.begin(), tails.end(), a[i]);
        const std::size_t position = static_cast<std::size_t>(it - tails.begin());
        if (position > 0) pred[i] = tail_index[position - 1];
        if (it == tails.end()) {
            tails.push_back(a[i]);
            tail_index.push_back(i);
        } else {
            *it = a[i];
            tail_index[position] = i;
        }
    }
    std::vector<int> indices;
    if (!tail_index.empty()) {
        for (int i = tail_index.back(); i != -1; i = pred[i]) indices.push_back(i);
    }
    std::reverse(indices.begin(), indices.end());
    return indices;
}

// Greedy que falla: recorrer tomando todo lo que sea mayor que lo último tomado.
inline int lis_greedy_take(const std::vector<int>& a) {
    int taken = 0;
    int last = 0;
    for (int x : a) {
        if (taken == 0 || x > last) {
            taken++;
            last = x;
        }
    }
    return taken;
}

// Árbitro: prueba los 2^n subconjuntos de posiciones.
inline int lis_brute(const std::vector<int>& a, bool strict = true) {
    const std::size_t n = a.size();
    int best = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        int count = 0;
        int last = 0;
        bool ok = true;
        for (std::size_t i = 0; i < n && ok; i++) {
            if (!(mask >> i & 1u)) continue;
            if (count > 0 && (strict ? a[i] <= last : a[i] < last)) ok = false;
            last = a[i];
            count++;
        }
        if (ok) best = std::max(best, count);
    }
    return best;
}