結果
| 問題 |
No.1435 Mmm......
|
| ユーザー |
 cutmdo
|
| 提出日時 | 2025-01-23 04:46:29 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 31,601 bytes |
| コンパイル時間 | 1,964 ms |
| コンパイル使用メモリ | 176,652 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2025-01-23 04:46:33 |
| 合計ジャッジ時間 | 3,373 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 4 |
| other | WA * 24 |
ソースコード
/*
* Author: cutmdo
* Created: 2025-01-23 04:46:18 UTC+09:00
*/
//=============================================================================================
#define dump(...)
#include <map>
#include <iomanip>
#include <stdexcept>
#include <list>
#include <iostream>
#include <ranges>
#include <cmath>
#include <memory>
#include <type_traits>
#include <random>
#include <bitset>
#include <set>
#include <deque>
#include <utility>
#include <vector>
#include <string>
#include <functional>
#include <numeric>
#include <algorithm>
namespace mtd { template <class S, S element, class op > requires std::is_invocable_r_v<S, op, S, S> struct Monoid { using value_type = S; constexpr static S _element = element; using op_type = op; S m_val; constexpr Monoid(S val) : m_val(val) {} constexpr Monoid() : Monoid(element) {} constexpr Monoid binaryOperation(const Monoid& m2) const { return op()(m_val, m2.m_val); } friend std::ostream& operator<<(std::ostream& os, const Monoid<S, element, op>& m) { return os << m.m_val; } }; namespace __detail { template <typename T, template <typename, auto, typename> typename S> concept is_monoid_specialization_of = requires { typename std::enable_if_t<std::is_same_v< T, S<typename T::value_type, T::_element, typename T::op_type>>>; }; } template <typename M> concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;}
namespace mtd { namespace util { template <class F, class T> constexpr auto tuple_transform(F&& f, T&& t) { return std::apply( [&]<class... Ts>(Ts&&... elems) { return std::tuple<std::invoke_result_t<F&, Ts>...>( std::invoke(f, std::forward<Ts>(elems))...); }, std::forward<T>(t)); } template <class F, class T> constexpr auto tuple_for_each(F&& f, T&& t) { std::apply( [&]<class... Ts>(Ts&&... elems) { (std::invoke(f, std::forward<Ts>(elems)), ...); }, std::forward<T>(t)); } } }
namespace mtd { template <class T, class S> inline auto chmax(T& t, const S& s) { if (s > t) { t = s; return true; } return false; } template <class T, class S> inline auto chmin(T& t, const S& s) { if (s < t) { t = s; return true; } return false; } template <class S> constexpr auto vec(S x) { return x; } template <class S, class... T> constexpr auto vec(S x, int n, T... ns) { return std::vector(n, vec(x, ns...)); }}
namespace mtd { template <monoid Monoid> class SegmentTree { private: const int m_size; std::vector<Monoid> m_node; using S = decltype(Monoid().m_val); constexpr int calcSize(int n) const { int size = 1; while (size < n) { size <<= 1; } return size; } template <class Lambda> constexpr auto _update_op(int itr, Monoid&& val, const Lambda& op) { int i = itr + m_size - 1; m_node[i] = op(m_node[i], std::forward<decltype(val)>(val)); while (i) { i = (i - 1) >> 1; m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]); } } constexpr auto _query(int _l, int _r) const { auto l = std::max(_l, 0) + m_size; auto r = std::min(_r, m_size - 1) + m_size; auto lm = Monoid(); auto rm = Monoid(); while (l <= r) { if (l & 1) { lm = lm.binaryOperation(m_node[l - 1]); ++l; } if (!(r & 1)) { rm = m_node[r - 1].binaryOperation(rm); --r; } l >>= 1, r >>= 1; } return lm.binaryOperation(rm); } constexpr auto _construct(const std::vector<S>& vec) { for (unsigned int i = 0; i < vec.size(); ++i) { m_node[i + m_size - 1] = Monoid(vec[i]); } for (int i = m_size - 2; i >= 0; --i) { m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]); } } public: SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {} SegmentTree(int n, const std::vector<S>& vec) : SegmentTree(n) { _construct(vec); } template <class Lambda> constexpr auto update_op(int itr, Monoid&& val, const Lambda& op) { return _update_op(itr, std::forward<Monoid>(val), op); } constexpr auto update(int itr, Monoid&& val) { return update_op(itr, std::forward<Monoid>(val), [](const Monoid&, const Monoid& m2) { return m2; }); } constexpr auto add(int itr, Monoid&& val) { return update_op(itr, std::forward<Monoid>(val), [](const Monoid& m1, const Monoid& m2) { return Monoid(m1.m_val + m2.m_val); }); } constexpr auto query(int l, int r) const { return _query(l, r).m_val; } constexpr auto query_all() const { return m_node[0].m_val; } /* * f([l, r]) = true となる最大のr * judge: (Monoid) -> bool **/ template <class F> constexpr auto max_right(int _l, const F& judge) const { if (!judge(Monoid())) { throw std::runtime_error("SegmentTree.max_right.judge(e) must be true"); } auto l = std::max(_l, 0) + m_size; auto r = 2 * m_size - 1; auto lm = Monoid(); while (l <= r) { if (l & 1) { auto next = lm.binaryOperation(m_node[l - 1]); if (!judge(next)) { auto itr = l; while (itr < m_size) { auto litr = 2 * itr; auto ritr = 2 * itr + 1; auto lval = lm.binaryOperation(m_node[litr - 1]); if (!judge(lval)) { itr = litr; } else { itr = ritr; std::swap(lm, lval); } } return itr - m_size - 1; } std::swap(lm, next); ++l; } l >>= 1, r >>= 1; } return m_size - 1; } /* * f([l, r]) = true となる最小のl * judge: (Monoid) -> bool **/ template <class F> constexpr auto min_left(int _r, const F& judge) const { if (!judge(Monoid())) { throw std::runtime_error("SegmentTree.min_left.judge(e) must be true"); } auto l = m_size; auto r = std::min(_r, m_size - 1) + m_size; auto rm = Monoid(); while (l <= r) { if (l & 1) { ++l; } if (!(r & 1) || (_r == m_size - 1 && r == 1)) { auto next = m_node[r - 1].binaryOperation(rm); if (!judge(next)) { auto itr = r; while (itr < m_size) { auto litr = 2 * itr; auto ritr = 2 * itr + 1; auto rval = m_node[ritr - 1].binaryOperation(rm); if (!judge(rval)) { itr = ritr; } else { itr = litr; std::swap(rm, rval); } } return itr - m_size + 1; } std::swap(rm, next); --r; } l >>= 1, r >>= 1; } return 0; } constexpr auto debug() const { for (int i = 0; i < m_size; ++i) { std::cout << m_node[m_size + i - 1] << " "; } std::cout << std::endl; } };}
namespace mtd { namespace io { namespace type { template <class T> struct vec { using value_type = T; }; template <class T> concept is_vec = requires { requires std::is_same_v<T, vec<typename T::value_type>>; }; template <class T> struct mat { using value_type = T; }; template <class T> concept is_mat = requires { requires std::is_same_v<T, mat<typename T::value_type>>; }; } template <class T> auto _input() { T x; std::cin >> x; return x; } template <typename T> requires requires { typename std::tuple_size<T>::type; } auto _input() { T x; util::tuple_for_each([](auto&& i) { std::cin >> i; }, x); return x; } template <type::is_vec T> auto _input(int n) { std::vector<typename T::value_type> v; v.reserve(n); for (auto i : std::views::iota(0, n)) { v.emplace_back(_input<typename T::value_type>()); } return v; } template <type::is_mat T> auto _input(int h, int w) { std::vector<std::vector<typename T::value_type>> mat; mat.reserve(h); for (auto i : std::views::iota(0, h)) { mat.emplace_back(_input<type::vec<typename T::value_type>>(w)); } return mat; } template <int N, class Tuple, class T, class... Args, class... Sizes> auto _tuple_input(Tuple& t, Sizes... sizes); template <int N, class Tuple, type::is_vec T, class... Args, class Size, class... Sizes> auto _tuple_input(Tuple& t, Size size, Sizes... sizes); template <int N, class Tuple, type::is_mat T, class... Args, class Size, class... Sizes> auto _tuple_input(Tuple& t, Size size_h, Size size_w, Sizes... sizes); template <int N, class Tuple, class T, class... Args, class... Sizes> auto _tuple_input(Tuple& t, Sizes... sizes) { std::get<N>(t) = _input<T>(); if constexpr (sizeof...(Args) > 0) { _tuple_input<N + 1, Tuple, Args...>(t, sizes...); } } template <int N, class Tuple, type::is_vec T, class... Args, class Size, class... Sizes> auto _tuple_input(Tuple& t, Size size, Sizes... sizes) { std::get<N>(t) = _input<T>(size); if constexpr (sizeof...(Args) > 0) { _tuple_input<N + 1, Tuple, Args...>(t, sizes...); } } template <int N, class Tuple, type::is_mat T, class... Args, class Size, class... Sizes> auto _tuple_input(Tuple& t, Size size_h, Size size_w, Sizes... sizes) { std::get<N>(t) = _input<T>(size_h, size_w); if constexpr (sizeof...(Args) > 0) { _tuple_input<N + 1, Tuple, Args...>(t, sizes...); } } template <class T> struct _Converter { using type = T; }; template <class T> struct _Converter<type::vec<T>> { using type = std::vector<T>; }; template <class T> struct _Converter<type::mat<T>> { using type = std::vector<std::vector<T>>; }; template <class... Args, class... Sizes> requires(std::convertible_to<Sizes, size_t>&&...) auto in(Sizes... sizes) { auto base = std::tuple<typename _Converter<Args>::type...>(); _tuple_input<0, decltype(base), Args...>(base, sizes...); return base; } } }
namespace mtd { namespace ranges { namespace __detail { template <typename... T> concept __all_random_access = (std::ranges::random_access_range<T> && ...); template <typename... T> concept __all_bidirectional = (std::ranges::bidirectional_range<T> && ...); template <typename... T> concept __all_forward = (std::ranges::forward_range<T> && ...); template <class... T> constexpr auto _S_iter_concept() { if constexpr (__all_random_access<T...>) { return std::random_access_iterator_tag{}; } else if constexpr (__all_bidirectional<T...>) { return std::bidirectional_iterator_tag{}; } else if constexpr (__all_forward<T...>) { return std::forward_iterator_tag{}; } else { return std::input_iterator_tag{}; } } } template <std::ranges::range... _Range> struct zip_view : public std::ranges::view_interface<zip_view<_Range...>> { class iterator { public: std::tuple<std::ranges::iterator_t<_Range>...> _M_current; using difference_type = int; using value_type = std::tuple< std::iter_reference_t<std::ranges::iterator_t<_Range>>...>; using iterator_concept = decltype(__detail::_S_iter_concept<_Range...>()); constexpr iterator() = default; constexpr explicit iterator(const decltype(_M_current)& __current) : _M_current(__current) {} constexpr auto operator*() const { return util::tuple_transform([](auto& __i) { return *__i; }, _M_current); } constexpr auto& operator++() { util::tuple_for_each([](auto& __i) { ++__i; }, _M_current); return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return ((std::get<_Is>(_M_current) == std::get<_Is>(other._M_current)) || ...); } (std::make_index_sequence<sizeof...(_Range)>{}); } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range...> { util::tuple_for_each([](auto& __i) { --__i; }, _M_current); return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range...> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range...> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range...> { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return std::ranges::min({difference_type( std::get<_Is>(_M_current) - std::get<_Is>(itr._M_current))...}); } (std::make_index_sequence<sizeof...(_Range)>{}); } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range...> { util::tuple_for_each([&n](auto& __i) { __i += n; }, _M_current); return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __tmp = *this; __tmp += n; return __tmp; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range...> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range...> { util::tuple_for_each([&n](auto& __i) { __i -= n; }, _M_current); return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __tmp = *this; __tmp -= n; return __tmp; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range...> { return util::tuple_transform([&n](auto& __i) { return __i[n]; }, _M_current); } }; class sentinel { public: std::tuple<std::ranges::sentinel_t<_Range>...> _M_end; constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return ( (std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...); } (std::make_index_sequence<sizeof...(_Range)>{}); } }; std::tuple<_Range...> _M_views; constexpr explicit zip_view(const _Range&... __views) : _M_views(__views...) {} constexpr auto begin() { return iterator(util::tuple_transform(std::ranges::begin, _M_views)); } constexpr auto end() { return sentinel(util::tuple_transform(std::ranges::end, _M_views)); } }; namespace __detail { template <typename T> auto _flatten(const T& t) { return std::make_tuple(t); } template <typename... T> auto _flatten(const std::tuple<T...>& t); template <typename Head, typename... Tail> auto _flatten_impl(const Head& head, const Tail&... tail) { return std::tuple_cat(_flatten(head), _flatten(tail)...); } template <typename... T> auto _flatten(const std::tuple<T...>& t) { return std::apply( [](const auto&... args) { return _flatten_impl(args...); }, t); } } template <std::ranges::range _Range> struct flatten_view : public std::ranges::view_interface<flatten_view<_Range>> { class iterator { public: std::ranges::iterator_t<_Range> _M_current; using difference_type = std::ranges::range_difference_t<_Range>; using value_type = decltype(__detail::_flatten( std::declval< std::iter_reference_t<std::ranges::iterator_t<_Range>>>())); using iterator_concept = decltype(__detail::_S_iter_concept<_Range>()); constexpr iterator() = default; constexpr explicit iterator(decltype(_M_current) __current) : _M_current(__current) {} constexpr auto operator*() const { return __detail::_flatten(*_M_current); } constexpr auto& operator++() { ++_M_current; return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return _M_current == other._M_current; } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range> { --_M_current; return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range> { return _M_current - itr._M_current; } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range> { _M_current += n; return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range> { auto __tmp = *this; __tmp += n; return __tmp; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range> { _M_current -= n; return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range> { auto __tmp = *this; __tmp -= n; return __tmp; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range> { return __detail::_flatten(_M_current[n]); } }; class sentinel { std::ranges::sentinel_t<_Range> _M_end; public: constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return __x._M_current == __y._M_end; } }; _Range _M_views; constexpr explicit flatten_view(const _Range& __views) : _M_views(__views) {} constexpr auto begin() { return iterator(std::ranges::begin(_M_views)); } constexpr auto end() { return sentinel(std::ranges::end(_M_views)); } }; template <std::ranges::range... _Range> struct cartesian_product_view : public std::ranges::view_interface< cartesian_product_view<_Range...>> { class iterator { public: using _Parent = cartesian_product_view; _Parent* _M_parent = nullptr; std::tuple<std::ranges::iterator_t<_Range>...> _M_current; using difference_type = int; using value_type = std::tuple< std::iter_reference_t<std::ranges::iterator_t<_Range>>...>; using iterator_concept = decltype(__detail::_S_iter_concept<_Range...>()); private: template <size_t _Nm = sizeof...(_Range) - 1> constexpr void _M_next() { auto& __it = std::get<_Nm>(_M_current); ++__it; if constexpr (_Nm > 0) if (__it == std::ranges::end(std::get<_Nm>(_M_parent->_M_views))) { __it = std::ranges::begin(std::get<_Nm>(_M_parent->_M_views)); _M_next<_Nm - 1>(); } } template <size_t _Nm = sizeof...(_Range) - 1> constexpr void _M_prev() { auto& __it = std::get<_Nm>(_M_current); if constexpr (_Nm > 0) if (__it == std::ranges::begin(std::get<_Nm>(_M_parent->_M_views))) { __it = std::ranges::end(std::get<_Nm>(_M_parent->_M_views)); _M_prev<_Nm - 1>(); } --__it; } template <size_t _Nm = sizeof...(_Range) - 1> constexpr void _M_advance(difference_type __x) requires __detail::__all_random_access<_Range...> { if (__x == 1) _M_next<_Nm>(); else if (__x == -1) _M_prev<_Nm>(); else if (__x != 0) { auto& __r = std::get<_Nm>(_M_parent->_M_views); auto& __it = std::get<_Nm>(_M_current); if constexpr (_Nm == 0) { __it += __x; } else { auto __size = std::ranges::ssize(__r); auto __begin = std::ranges::begin(__r); auto __offset = __it - __begin; __offset += __x; __x = __offset / __size; __offset %= __size; if (__offset < 0) { __offset = __size + __offset; --__x; } __it = __begin + __offset; _M_advance<_Nm - 1>(__x); } } } public: constexpr iterator() = default; constexpr explicit iterator(_Parent& __parent, const decltype(_M_current)& __current) : _M_parent(std::addressof(__parent)), _M_current(__current) {} constexpr auto operator*() const { return util::tuple_transform([](auto& __i) { return *__i; }, _M_current); } constexpr auto& operator++() { _M_next(); return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return ((std::get<_Is>(_M_current) == std::get<_Is>(other._M_current)) || ...); } (std::make_index_sequence<sizeof...(_Range)>{}); } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range...> { _M_prev(); return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range...> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range...> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range...> { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return std::ranges::min({difference_type( std::get<_Is>(_M_current) - std::get<_Is>(itr._M_current))...}); } (std::make_index_sequence<sizeof...(_Range)>{}); } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range...> { _M_advance(n); return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __tmp = *this; __tmp += n; return __tmp; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range...> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range...> { *this += -n; return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __tmp = *this; __tmp -= n; return __tmp; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range...> { return util::tuple_transform([&n](auto& __i) { return __i[n]; }, _M_current); } }; class sentinel { public: std::tuple<std::ranges::sentinel_t<_Range>...> _M_end; constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return ( (std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...); } (std::make_index_sequence<sizeof...(_Range)>{}); } }; std::tuple<_Range...> _M_views; constexpr explicit cartesian_product_view(const _Range&... __views) : _M_views(__views...) {} constexpr auto begin() { return iterator(*this, util::tuple_transform(std::ranges::begin, _M_views)); } constexpr auto end() { return sentinel(util::tuple_transform(std::ranges::end, _M_views)); } }; } namespace views { namespace __detail { template <typename... _Args> concept __can_zip_view = requires { ranges::zip_view(std::declval<_Args>()...); }; template <typename... _Args> concept __can_flatten_view = requires { ranges::flatten_view(std::declval<_Args>()...); }; template <typename... _Args> concept __can_cartesian_product_view = requires { ranges::cartesian_product_view(std::declval<_Args>()...); }; } struct _ZipView { template <class... _Tp> requires __detail::__can_zip_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::zip_view(std::forward<_Tp>(__e)...); } }; struct _Enumerate : std::views::__adaptor::_RangeAdaptorClosure { template <class _Tp> requires __detail::__can_zip_view<std::ranges::iota_view<size_t>, _Tp> constexpr auto operator() [[nodiscard]] (_Tp&& __e) const { return ranges::zip_view{std::views::iota(0), std::forward<_Tp>(__e)}; } static constexpr bool _S_has_simple_call_op = true; }; struct _Flatten : std::views::__adaptor::_RangeAdaptorClosure { template <class... _Tp> requires __detail::__can_flatten_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::flatten_view(std::forward<_Tp>(__e)...); } static constexpr bool _S_has_simple_call_op = true; }; struct _CartesianProduct { template <class... _Tp> requires __detail::__can_cartesian_product_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::cartesian_product_view(std::forward<_Tp>(__e)...); } }; struct _ProductN { template <class... _Tp> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::cartesian_product_view(std::views::iota(0, __e)...); } }; inline constexpr _ZipView zip{}; inline constexpr _Enumerate enumerate{}; inline constexpr _Flatten flatten{}; inline constexpr _CartesianProduct cartesian_product{}; inline constexpr _ProductN product_n{}; } }
namespace mtd { namespace ranges { constexpr int _inf = 1e9; template <class... Args> struct istream_view : public std::ranges::view_interface<istream_view<Args...>> { class iterator { int count; std::tuple<typename io::_Converter<Args>::type...> val; public: using difference_type = int; using value_type = decltype(val); using iterator_concept = std::input_iterator_tag; constexpr iterator() = default; constexpr explicit iterator(int _count) : count(_count) { operator++(); } constexpr auto operator*() const { return val; } constexpr auto& operator++() { --count; if (count >= 0) { val = io::in<Args...>(); } return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& s) const { return count == s.count; } constexpr auto operator==(std::default_sentinel_t) const { return count < 0 || std::cin.eof() || std::cin.fail() || std::cin.bad(); } constexpr friend auto operator==(std::default_sentinel_t s, const iterator& li) { return li == s; } }; int count; public: constexpr explicit istream_view(int _count) : count(_count) {} constexpr explicit istream_view() : istream_view(_inf) {} constexpr auto begin() const { return iterator(count); } constexpr auto end() const { return std::default_sentinel; } }; } namespace views { namespace __detail { template <typename... _Args> concept __can_istream_view = requires { ranges::istream_view(std::declval<_Args>()...); }; } template <class... Args> struct _Istream { template <class... _Tp> requires __detail::__can_istream_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::istream_view<Args...>(std::forward<_Tp>(__e)...); } }; template <class... Args> inline constexpr _Istream<Args...> istream{}; } }
namespace mtd { struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; } _Preprocessing; template <class T> using tvec = mtd::io::type::vec<T>; template <class T> using tmat = mtd::io::type::mat<T>; using mtd::io::in; template <class... Args> inline constexpr auto ins = mtd::views::istream<Args...>;}
//=============================================================================================
using ll = long long;
signed main() {
std::vector<ll> a(8);
std::iota(a.begin(), a.end(), 1);
auto op = [](ll a, ll b) { return std::min(a, b); };
using M = mtd::Monoid<ll, 1LL << 31, decltype(op)>;
auto segtree = mtd::SegmentTree<M>(8, a);
int line;
std::cin >> line;
dump(line, a);
auto judge = [&](const M& m) { return m.m_val >= line; };
auto l = segtree.min_left(7, judge) + 1;
dump(l);
}