Longest increasing subsequence (tools/lis.hpp)

(1)

int lis::segtree<true>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
int lis::segtree<true, false>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
int lis::bisect<true>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
int lis::bisect<true, false>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});

Given a sequence $(a_0, a_1, \ldots, a_{N - 1})$, it returns the length of the longest increasing subsequence. The relationship $a_i < a_j$ is defined by $\mathrm{comp}(a_i, a_j)$.

Constraints

comp is strict weak ordering.

Time Complexity

$O(N \log N)$

Algorithm

In the segtree function, it speeds up the DP of $O(N^2)$ time, which maximizes the length of the increasing subsequence when the last element of the increasing subsequence is $a_i$, to $O(N \log N)$ time using a segment tree. In the bisect function, it sppeds up the DP of $O(N^2)$ time, which minimizes the last element of the increasing subsequence when the length of the increasing subsequence is $l$, to $O(N \log N)$ time using binary search.

License

Author

anqooqie

(2)

int lis::segtree<false>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
int lis::segtree<false, false>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
int lis::bisect<false>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
int lis::bisect<false, false>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});

Given a sequence $(a_0, a_1, \ldots, a_{N - 1})$, it returns the length of the longest non-decreasing subsequence. The relationship $a_i \leq a_j$ is defined by $\lnot \mathrm{comp}(a_j, a_i)$.

Constraints

comp is strict weak ordering.

Time Complexity

$O(N \log N)$

Algorithm

See (1).

License

Author

anqooqie

(3)

std::vector<int> lis::segtree<true, true>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
std::vector<int> lis::bisect<true, true>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});

Given a sequence $(a_0, a_1, \ldots, a_{N - 1})$, it returns the indices of the longest increasing subsequence. Since there can be multiple longest increasing subsequences, the one with the smallest index sequence in lexicographic order is returned.

Formally speaking, it returns the smallest integer sequence $(i_0, i_1, \ldots, i_{k - 1})$ in lexicographic order that satisfy the following conditions:

\[\begin{align*} i_0 < i_1 < \cdots < l_{k - 1}\\ a_{i_0} < a_{i_1} < \cdots < a_{i_{k - 1}} \end{align*}\]

where $k$ is the length of the longest increasing subsequence, and the relationship $a_i < a_j$ is defined by $\mathrm{comp}(a_i, a_j)$.

Constraints

comp is strict weak ordering.

Time Complexity

$O(N \log N)$

Algorithm

See (1).

License

Author

anqooqie

(4)

std::vector<int> lis::segtree<false, true>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});
std::vector<int> lis::bisect<false, true>(InputIterator begin, InputIterator end, Compare comp = std::less<typename std::iterator_traits<InputIterator>::value_type>{});

Given a sequence $(a_0, a_1, \ldots, a_{N - 1})$, it returns the indices of the longest non-decreasing subsequence. Since there can be multiple longest non-decreasing subsequences, the one with the smallest index sequence in lexicographic order is returned.

Formally speaking, it returns the smallest integer sequence $(i_0, i_1, \ldots, i_{k - 1})$ in lexicographic order that satisfy the following conditions:

\[\begin{align*} i_0 < i_1 < \cdots < l_{k - 1}\\ a_{i_0} \leq a_{i_1} \leq \cdots \leq a_{i_{k - 1}} \end{align*}\]

where $k$ is the length of the longest non-decreasing subsequence, and the relationship $a_i \leq a_j$ is defined by $\lnot \mathrm{comp}(a_j, a_i)$.

Constraints

comp is strict weak ordering.

Time Complexity

$O(N \log N)$

Algorithm

See (1).

License

Author

anqooqie

Depends on

Verified with

Code

#ifndef TOOLS_LIS_HPP
#define TOOLS_LIS_HPP

#include <type_traits>
#include <iterator>
#include <cstddef>
#include <vector>
#include <numeric>
#include <algorithm>
#include <utility>
#include <functional>
#include "atcoder/segtree.hpp"
#include "tools/permutation.hpp"
#include "tools/monoid.hpp"

namespace tools {
  namespace lis {
    template <bool Strict, bool Restore, typename RandomAccessIterator, typename Compare, ::std::enable_if_t<::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<RandomAccessIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> segtree(const RandomAccessIterator begin, const RandomAccessIterator end, const Compare& comp) {
      const int N = end - begin;

      const auto p = ::tools::permutation<int>([&]() {
        ::std::vector<int> v(N);
        if constexpr (Strict) {
          ::std::iota(v.rbegin(), v.rend(), 0);
        } else {
          ::std::iota(v.begin(), v.end(), 0);
        }
        ::std::stable_sort(v.begin(), v.end(), [&](const auto x, const auto y) {
          return comp(begin[x], begin[y]);
        });
        return v;
      }()).inv_inplace();

      ::atcoder::segtree<int, ::tools::monoid::max<int, 0>::op, ::tools::monoid::max<int, 0>::e> segtree(N);
      for (int i = 0; i < N; ++i) {
        segtree.set(p[i], segtree.prod(0, p[i]) + 1);
      }

      if constexpr (Restore) {
        ::std::vector<int> answer(segtree.all_prod(), -1);
        for (int i = N - 1; i >= 0; --i) {
          if (const auto k = segtree.get(p[i]); k == segtree.all_prod() || (answer[k] >= 0 && p[i] < p[answer[k]])) {
            answer[k - 1] = i;
          }
        }
        return answer;
      } else {
        return segtree.all_prod();
      }
    }
    template <bool Strict, bool Restore, typename InputIterator, typename Compare, ::std::enable_if_t<!::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<InputIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> segtree(const InputIterator begin, const InputIterator end, const Compare& comp) {
      ::std::vector<typename ::std::iterator_traits<InputIterator>::value_type> v(begin, end);
      return ::tools::lis::segtree<Strict, Restore>(v.begin(), v.end());
    }
    template <bool Strict, bool Restore, typename InputIterator>
    ::std::conditional_t<Restore, ::std::vector<int>, int> segtree(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::segtree<Strict, Restore>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }
    template <bool Strict, typename InputIterator, typename Compare>
    int segtree(const InputIterator begin, const InputIterator end, const Compare& comp) {
      return ::tools::lis::segtree<Strict, false>(begin, end, comp);
    }
    template <bool Strict, typename InputIterator>
    int segtree(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::segtree<Strict, false>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }

    template <bool Strict, bool Restore, typename RandomAccessIterator, typename Compare, ::std::enable_if_t<::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<RandomAccessIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> bisect(const RandomAccessIterator begin, const RandomAccessIterator end, const Compare& comp) {
      const int N = end - begin;

      ::std::vector<int> bisect;
      ::std::vector<int> lengths(Restore ? N : 0);
      for (int i = 0; i < N; ++i) {
        const auto it = Strict
          ? ::std::lower_bound(bisect.begin(), bisect.end(), i, [&](const auto x, const auto y) { return comp(begin[x], begin[y]); })
          : ::std::upper_bound(bisect.begin(), bisect.end(), i, [&](const auto x, const auto y) { return comp(begin[x], begin[y]); });
        if constexpr (Restore) {
          lengths[i] = ::std::distance(bisect.begin(), it) + 1;
        }
        if (it != bisect.end()) {
          *it = i;
        } else {
          bisect.push_back(i);
        }
      }

      if constexpr (Restore) {
        ::std::vector<int> answer(bisect.size(), -1);
        for (int i = N - 1; i >= 0; --i) {
          if (const auto k = lengths[i]; ::std::cmp_equal(k, bisect.size()) || (answer[k] >= 0 && (Strict ? comp(begin[i], begin[answer[k]]) : !comp(begin[answer[k]], begin[i])))) {
            answer[k - 1] = i;
          }
        }
        return answer;
      } else {
        return bisect.size();
      }
    }
    template <bool Strict, bool Restore, typename InputIterator, typename Compare, ::std::enable_if_t<!::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<InputIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> bisect(const InputIterator begin, const InputIterator end, const Compare& comp) {
      ::std::vector<typename ::std::iterator_traits<InputIterator>::value_type> v(begin, end);
      return ::tools::lis::bisect<Strict, Restore>(v.begin(), v.end());
    }
    template <bool Strict, bool Restore, typename InputIterator>
    ::std::conditional_t<Restore, ::std::vector<int>, int> bisect(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::bisect<Strict, Restore>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }
    template <bool Strict, typename InputIterator, typename Compare>
    int bisect(const InputIterator begin, const InputIterator end, const Compare& comp) {
      return ::tools::lis::bisect<Strict, false>(begin, end, comp);
    }
    template <bool Strict, typename InputIterator>
    int bisect(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::bisect<Strict, false>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }
  }
}

#endif

#line 1 "tools/lis.hpp"



#include <type_traits>
#include <iterator>
#include <cstddef>
#include <vector>
#include <numeric>
#include <algorithm>
#include <utility>
#include <functional>
#line 1 "lib/ac-library/atcoder/segtree.hpp"



#line 5 "lib/ac-library/atcoder/segtree.hpp"
#include <cassert>
#line 8 "lib/ac-library/atcoder/segtree.hpp"

#line 1 "lib/ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "lib/ac-library/atcoder/segtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder


#line 1 "tools/permutation.hpp"



#line 7 "tools/permutation.hpp"
#include <iostream>
#line 10 "tools/permutation.hpp"
#include <ranges>
#line 13 "tools/permutation.hpp"

namespace tools {
  template <typename T>
  class permutation {
    ::std::vector<int> m_perm;
    ::std::vector<int> m_inv;

    void verify_consistency() const {
#ifndef NDEBUG
      ::std::vector<bool> unique(this->size(), true);
      for (const auto x : this->m_perm) {
        assert(0 <= x && x < this->size());
        assert(unique[x]);
        unique[x] = false;
      }
#endif
    }

    void make_inv() {
      this->m_inv.resize(this->size());
      for (int i = 0; i < this->size(); ++i) {
        this->m_inv[this->m_perm[i]] = i;
      }
    }

  public:
    class iterator {
      ::std::vector<int>::const_iterator m_it;

    public:
      using reference = T;
      using value_type = T;
      using difference_type = ::std::ptrdiff_t;
      using pointer = const value_type*;
      using iterator_category = ::std::random_access_iterator_tag;

      iterator() = default;
      iterator(const ::std::vector<int>::const_iterator it) : m_it(it) {
      }

      reference operator*() const {
        return *this->m_it;
      }

      iterator& operator++() {
        ++this->m_it;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_it;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_it += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_it -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_it + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_it - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        return lhs.m_it - rhs.m_it;
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend bool operator==(const iterator lhs, const iterator rhs) {
        return lhs.m_it == rhs.m_it;
      }
      friend bool operator!=(const iterator lhs, const iterator rhs) {
        return lhs.m_it != rhs.m_it;
      }
      friend bool operator<(const iterator lhs, const iterator rhs) {
        return lhs.m_it < rhs.m_it;
      }
      friend bool operator<=(const iterator lhs, const iterator rhs) {
        return lhs.m_it <= rhs.m_it;
      }
      friend bool operator>(const iterator lhs, const iterator rhs) {
        return lhs.m_it > rhs.m_it;
      }
      friend bool operator>=(const iterator lhs, const iterator rhs) {
        return lhs.m_it >= rhs.m_it;
      }
    };

    permutation() = default;
    explicit permutation(const int n) : m_perm(n), m_inv(n) {
      ::std::iota(this->m_perm.begin(), this->m_perm.end(), 0);
      ::std::iota(this->m_inv.begin(), this->m_inv.end(), 0);
    }
    template <::std::ranges::range R>
    permutation(R&& r) : m_perm(::std::ranges::begin(r), ::std::ranges::end(r)) {
      this->verify_consistency();
      this->make_inv();
    }

    int size() const {
      return this->m_perm.size();
    }
    T operator[](const int i) const {
      assert(0 <= i && i < this->size());
      return this->m_perm[i];
    }
    iterator begin() const {
      return this->m_perm.begin();
    }
    iterator end() const {
      return this->m_perm.end();
    }

    ::tools::permutation<T>& swap_from_left(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      this->m_inv[this->m_perm[y]] = x;
      this->m_inv[this->m_perm[x]] = y;
      ::std::swap(this->m_perm[x], this->m_perm[y]);
      return *this;
    }
    ::tools::permutation<T>& swap_from_right(const int x, const int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());
      this->m_perm[this->m_inv[y]] = x;
      this->m_perm[this->m_inv[x]] = y;
      ::std::swap(this->m_inv[x], this->m_inv[y]);
      return *this;
    }

    long long id() const {
      if (this->size() == 0) return 0;

      ::std::vector<int> left(this->size());
      ::std::iota(left.begin(), left.end(), 0);

      ::std::vector<long long> fact(this->size());
      fact[0] = 1;
      for (int i = 1; i < this->size(); ++i) {
        fact[i] = fact[i - 1] * i;
      }

      long long id = 0;
      for (int i = 0; i < this->size(); ++i) {
        auto it = ::std::lower_bound(left.begin(), left.end(), this->m_perm[i]);
        id += ::std::distance(left.begin(), it) * fact[this->size() - 1 - i];
        left.erase(it);
      }

      return id;
    }

    static ::tools::permutation<T> from(const int n, long long id) {
      if (n == 0) return ::tools::permutation<T>(0);

      ::std::vector<int> left(n);
      ::std::iota(left.begin(), left.end(), 0);

      ::std::vector<long long> fact(n);
      fact[0] = 1;
      for (int i = 1; i < n; ++i) {
        fact[i] = fact[i - 1] * i;
      }

      ::std::vector<int> p;
      for (int i = 0; i < n; ++i) {
        const auto it = ::std::next(left.begin(), id / fact[n - i - 1]);
        p.push_back(*it);
        left.erase(it);
        id %= fact[n - i - 1];
      }

      return ::tools::permutation<T>(p);
    }

    ::tools::permutation<T> inv() const {
      return ::tools::permutation<T>(this->m_inv);
    }
    ::tools::permutation<T>& inv_inplace() {
      this->m_perm.swap(this->m_inv);
      return *this;
    }
    T inv(const int i) const {
      assert(0 <= i && i < this->size());
      return this->m_inv[i];
    }

    ::tools::permutation<T>& operator*=(const ::tools::permutation<T>& other) {
      assert(this->size() == other.size());
      for (int i = 0; i < this->size(); ++i) {
        this->m_inv[i] = other.m_perm[this->m_perm[i]];
      }
      this->m_perm.swap(this->m_inv);
      this->make_inv();
      return *this;
    }
    friend ::tools::permutation<T> operator*(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return ::tools::permutation<T>(lhs) *= rhs;
    }

    friend bool operator==(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return lhs.m_perm == rhs.m_perm;
    }
    friend bool operator!=(const ::tools::permutation<T>& lhs, const ::tools::permutation<T>& rhs) {
      return lhs.m_perm != rhs.m_perm;
    }

    friend ::std::ostream& operator<<(::std::ostream& os, const ::tools::permutation<T>& self) {
      os << '(';
      auto it = self.begin();
      const auto end = self.end();
      if (it != end) {
        os << *it;
        for (++it; it != end; ++it) {
          os << ", " << *it;
        }
      }
      return os << ')';
    }
    friend ::std::istream& operator>>(::std::istream& is, ::tools::permutation<T>& self) {
      for (auto& value : self.m_perm) {
        is >> value;
      }
      self.verify_consistency();
      self.make_inv();
      return is;
    }
  };
}


#line 1 "tools/monoid.hpp"



#line 6 "tools/monoid.hpp"
#include <limits>
#line 1 "tools/gcd.hpp"



#line 6 "tools/gcd.hpp"

namespace tools {
  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 9 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 15 "tools/lis.hpp"

namespace tools {
  namespace lis {
    template <bool Strict, bool Restore, typename RandomAccessIterator, typename Compare, ::std::enable_if_t<::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<RandomAccessIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> segtree(const RandomAccessIterator begin, const RandomAccessIterator end, const Compare& comp) {
      const int N = end - begin;

      const auto p = ::tools::permutation<int>([&]() {
        ::std::vector<int> v(N);
        if constexpr (Strict) {
          ::std::iota(v.rbegin(), v.rend(), 0);
        } else {
          ::std::iota(v.begin(), v.end(), 0);
        }
        ::std::stable_sort(v.begin(), v.end(), [&](const auto x, const auto y) {
          return comp(begin[x], begin[y]);
        });
        return v;
      }()).inv_inplace();

      ::atcoder::segtree<int, ::tools::monoid::max<int, 0>::op, ::tools::monoid::max<int, 0>::e> segtree(N);
      for (int i = 0; i < N; ++i) {
        segtree.set(p[i], segtree.prod(0, p[i]) + 1);
      }

      if constexpr (Restore) {
        ::std::vector<int> answer(segtree.all_prod(), -1);
        for (int i = N - 1; i >= 0; --i) {
          if (const auto k = segtree.get(p[i]); k == segtree.all_prod() || (answer[k] >= 0 && p[i] < p[answer[k]])) {
            answer[k - 1] = i;
          }
        }
        return answer;
      } else {
        return segtree.all_prod();
      }
    }
    template <bool Strict, bool Restore, typename InputIterator, typename Compare, ::std::enable_if_t<!::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<InputIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> segtree(const InputIterator begin, const InputIterator end, const Compare& comp) {
      ::std::vector<typename ::std::iterator_traits<InputIterator>::value_type> v(begin, end);
      return ::tools::lis::segtree<Strict, Restore>(v.begin(), v.end());
    }
    template <bool Strict, bool Restore, typename InputIterator>
    ::std::conditional_t<Restore, ::std::vector<int>, int> segtree(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::segtree<Strict, Restore>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }
    template <bool Strict, typename InputIterator, typename Compare>
    int segtree(const InputIterator begin, const InputIterator end, const Compare& comp) {
      return ::tools::lis::segtree<Strict, false>(begin, end, comp);
    }
    template <bool Strict, typename InputIterator>
    int segtree(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::segtree<Strict, false>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }

    template <bool Strict, bool Restore, typename RandomAccessIterator, typename Compare, ::std::enable_if_t<::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<RandomAccessIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> bisect(const RandomAccessIterator begin, const RandomAccessIterator end, const Compare& comp) {
      const int N = end - begin;

      ::std::vector<int> bisect;
      ::std::vector<int> lengths(Restore ? N : 0);
      for (int i = 0; i < N; ++i) {
        const auto it = Strict
          ? ::std::lower_bound(bisect.begin(), bisect.end(), i, [&](const auto x, const auto y) { return comp(begin[x], begin[y]); })
          : ::std::upper_bound(bisect.begin(), bisect.end(), i, [&](const auto x, const auto y) { return comp(begin[x], begin[y]); });
        if constexpr (Restore) {
          lengths[i] = ::std::distance(bisect.begin(), it) + 1;
        }
        if (it != bisect.end()) {
          *it = i;
        } else {
          bisect.push_back(i);
        }
      }

      if constexpr (Restore) {
        ::std::vector<int> answer(bisect.size(), -1);
        for (int i = N - 1; i >= 0; --i) {
          if (const auto k = lengths[i]; ::std::cmp_equal(k, bisect.size()) || (answer[k] >= 0 && (Strict ? comp(begin[i], begin[answer[k]]) : !comp(begin[answer[k]], begin[i])))) {
            answer[k - 1] = i;
          }
        }
        return answer;
      } else {
        return bisect.size();
      }
    }
    template <bool Strict, bool Restore, typename InputIterator, typename Compare, ::std::enable_if_t<!::std::is_base_of_v<::std::random_access_iterator_tag, typename ::std::iterator_traits<InputIterator>::iterator_category>, ::std::nullptr_t> = nullptr>
    ::std::conditional_t<Restore, ::std::vector<int>, int> bisect(const InputIterator begin, const InputIterator end, const Compare& comp) {
      ::std::vector<typename ::std::iterator_traits<InputIterator>::value_type> v(begin, end);
      return ::tools::lis::bisect<Strict, Restore>(v.begin(), v.end());
    }
    template <bool Strict, bool Restore, typename InputIterator>
    ::std::conditional_t<Restore, ::std::vector<int>, int> bisect(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::bisect<Strict, Restore>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }
    template <bool Strict, typename InputIterator, typename Compare>
    int bisect(const InputIterator begin, const InputIterator end, const Compare& comp) {
      return ::tools::lis::bisect<Strict, false>(begin, end, comp);
    }
    template <bool Strict, typename InputIterator>
    int bisect(const InputIterator begin, const InputIterator end) {
      return ::tools::lis::bisect<Strict, false>(begin, end, ::std::less<typename ::std::iterator_traits<InputIterator>::value_type>{});
    }
  }
}