#include /* #expanded [template.hpp] */ /* #expanded [aliases.hpp] */ /* #expanded [types.hpp] */ using ll = long long;using ull = unsigned long long;using ld = long double; /* [types.hpp] */ #define until(...) while(!(__VA_ARGS__)) #define ALL(x) std::begin((x)),std::end((x)) #define RALL(x) std::rbegin((x)),std::rend((x)) #define $F first #define $S second constexpr char ln = '\n';constexpr char spc = ' '; #include constexpr std::pair DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };constexpr std::pair DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };template inline auto mod(T1 x, T2 r) { return (x%r+r)%r; }template inline bool chmax(T1 &a, T2 b) { return (a inline bool chmin(T1 &a, T2 b) { return (a>b ? a=b, true : false); } /* [aliases.hpp] */ /* #expanded [iterations.hpp] */ /* #expanded [overload.hpp] */ #define $OVERLOAD2(arg0, arg1, cmd, ...) cmd #define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd #define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd #define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd /* [overload.hpp] */ #define LOOP(n) REPI($_, (n)) #define REPI(i,n) for(int i=0, i##_length=int(n); i=0;) #define REPB(i,l,r) for(auto i=(r), i##_last=(l); --i>=i##_last;) #define REPRS(i,l,r,s) for(auto i=(r), i##_last=(l); (i-=(s))>=i##_last;) #define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__) #define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__) #define FORI(i,l,r) for(auto i=(l), i##_last=(r); i<=i##_last; ++i) #define FORIS(i,l,r,s) for(auto i=(l), i##_last=(r); i<=i##_last; i+=(s)) #define FORR(i,l,r) for(auto i=(r), i##_last=(l); i>=i##_last; --i) #define FORRS(i,l,r,s) for(auto i=(r), i##_last=(l); i>=i##_last; i-=(s)) #define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI)(__VA_ARGS__) #define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR)(__VA_ARGS__) #define ITR1(e0,v) for(const auto &e0 : (v)) #define ITRP1(e0,v) for(auto e0 : (v)) #define ITRR1(e0,v) for(auto &e0 : (v)) #define ITR2(e0,e1,v) for(const auto [e0, e1] : (v)) #define ITRP2(e0,e1,v) for(auto [e0, e1] : (v)) #define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v)) #define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v)) #define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v)) #define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v)) #define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v)) #define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v)) #define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v)) #define ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__) #define ITRP(...) $OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__) #define ITRR(...) $OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__) /* [iterations.hpp] */ /* #expanded [fast_io.hpp] */ #include #ifdef __GNUC__ __attribute__((constructor)) inline void fast_io() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); } #else inline void fast_io() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); } #endif /* [fast_io.hpp] */ #ifdef LOCAL_JUDGE #include #define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__) #define DEBUG(...) do { debugger::DEBUG(nullptr, "\033[3;35m#" + to_string(__LINE__) + "\033[m "); debugger::DEBUG(__VA_ARGS__); debugger::DEBUG(nullptr, "\033[m\n"); } while(0); #else #define debug(...) ({ ; }) #define DEBUG(...) ({ ; }) #endif /* #expanded [input.hpp] */ #include #include #include #include #include #include /* #expanded [resolving_rank.hpp] */ namespace lib {namespace internal {template struct resolving_rank : resolving_rank {};template<> struct resolving_rank<0> {};}} /* [resolving_rank.hpp] */ templatestruct input_adapter {private:templateauto _set(lib::internal::resolving_rank<3>, T *const val) -> decltype(std::declval() >> *val, 0) {*this->in >> *val;return 0;}templateauto _set(lib::internal::resolving_rank<2>, T *const val) -> decltype(std::begin(*val), std::end(*val), 0) {(*this)(std::begin(*val), std::end(*val));return 0;}templateauto _set(lib::internal::resolving_rank<1>, T *const val) -> decltype(val->first, val->second, 0) {(*this)(&*val);return 0;}templateauto _set(lib::internal::resolving_rank<0>, T *const val) -> std::enable_if_t::value,int> {long long v; std::cin >> v;*val = { v };return 0;}protected:templatesource *set(T *const val) {this->_set(lib::internal::resolving_rank<3>{}, val);return this->in;}public:using char_type = typename source::char_type;source *in;input_adapter(source *in = &std::cin) : in(in) {}template inline input_adapter& operator>>(T &s) {this->set(&s);return *this;}template inline T one() {T val; *this >> val;return val;}template inline void operator()(T*const val) {*this >> *val;}template inline void operator()(T*const head, Args*const ...tail) {*this >> *head;(*this)(tail...);}template inline void operator()(I first, I last) {for(I itr=first; itr!=last; ++itr) *this >> *itr;}template inline void operator()(std::pair *const p) {(*this)(&p->first, &p->second);}}; /* [input.hpp] */ /* #expanded [output.hpp] */ #include #include #include templatestruct output_adapter {private:templateauto _put(lib::internal::resolving_rank<2>, const T &val) -> decltype(std::declval() << val, 0) {*this->out << val;return 0;}templateauto _put(lib::internal::resolving_rank<1>, const T &val) -> decltype(val.val(), 0) {*this->out << val.val();return 0;}templateauto _put(lib::internal::resolving_rank<0>, const T &val) -> decltype(std::begin(val), std::end(val), 0) {(*this)(std::begin(val), std::end(val), false);return 0;}protected:templatedestination *put(const T &val) {this->_put(lib::internal::resolving_rank<2>{}, val);return this->out;}public:using char_type = typename destination::char_type;static constexpr auto sendl = std::endl>;destination *out;Terminator endline;Separator separator;output_adapter(destination *out = &std::cout, Terminator endline = "\n", Separator separator = " "): out(out), endline(endline), separator(separator) {}inline void seekp(const typename destination::off_type off, const std::ios_base::seekdir dir = std::ios_base::cur) { this->out->seekp(off, dir); };template inline output_adapter& operator<<(const T &s) {this->put(s);return *this;}template inline void operator()(const T &val = "") {*this << val << this->endline;}template inline void operator()(const T &head, const Args& ...tail) {*this << head << this->separator;(*this)(tail...);}template inline void operator()(const I first, const I last, const bool terminate = true) {for(I itr=first; itr!=last;) {*this << *itr;if(++itr == last) {if(terminate) *this << this->endline;}else *this << this->separator;}}template inline void operator()(const std::initializer_list vals) {std::vector wrapped(vals.begin(), vals.end());(*this)(wrapped.begin(), wrapped.end());}template inline void operator()(const std::pair &p) {(*this)(p.first, p.second);}}; /* [output.hpp] */ input_adapter _input;output_adapter _print; #define input _input #define print _print /* [template.hpp] */ /* #expanded [wavelet_matrix.hpp] */ #include #include #include #include #include #include #include #include #include #include /* #expanded [dev_assert.hpp] */ #ifdef LOCAL_JUDGE #include #define dev_assert(...) assert(__VA_ARGS__) #else #define dev_assert(...) ({ ; }) #endif /* [dev_assert.hpp] */ /* #expanded [types.hpp] */ #include namespace lib {namespace internal {using size_t = std::int32_t;using int128_t = __int128_t;using uint128_t = __uint128_t;}} /* [types.hpp] */ /* #expanded [iterator.hpp] */ #include namespace lib {namespace internal {templatestruct iterator_interface {using iterator_category = std::output_iterator_tag;using difference_type = size_t;using value_type = T;using pointer = T*;using reference = T&;virtual T operator*() const = 0;};templatestruct bidirectiona_iterator_interface : iterator_interface {using iterator_category = std::bidirectional_iterator_tag;virtual bidirectiona_iterator_interface& operator++() = 0;virtual bidirectiona_iterator_interface& operator--() = 0;};templatestruct random_access_iterator_base : bidirectiona_iterator_interface {using iterator_category = std::random_access_iterator_tag;using difference_type = typename bidirectiona_iterator_interface::difference_type;public:virtual random_access_iterator_base& operator+=(const difference_type count) = 0;virtual random_access_iterator_base& operator-=(const difference_type count) = 0;};templatestruct container_iterator_interface : public random_access_iterator_base {using difference_type = typename bidirectiona_iterator_interface::difference_type;protected:const container *const _ref;difference_type _pos;container_iterator_interface(const container *const ref, const difference_type& pos) : _ref(ref), _pos(pos) {}public:inline const container * ref() const { return this->_ref; }inline difference_type pos() const { return this->_pos; }inline difference_type& pos() { return this->_pos; }inline container_iterator_interface& operator++() override { return ++this->pos(), *this; }inline container_iterator_interface& operator--() override { return --this->pos(), *this; }inline container_iterator_interface& operator+=(const difference_type count) override { return this->pos() += count, *this; }inline container_iterator_interface& operator-=(const difference_type count) override { return this->pos() -= count, *this; }inline difference_type operator-(const container_iterator_interface& other) const { return this->pos() - other.pos(); }inline bool operator<(const container_iterator_interface& other) const { return *this - other < 0; }inline bool operator>(const container_iterator_interface& other) const { return *this - other > 0; }inline bool operator<=(const container_iterator_interface& other) const { return not (*this > other); }inline bool operator>=(const container_iterator_interface& other) const { return not (*this < other); }inline bool operator!=(const container_iterator_interface& other) const { return this->ref() != other.ref() or *this < other or *this > other; }inline bool operator==(const container_iterator_interface& other) const { return not (*this != other); }};}} /* [iterator.hpp] */ /* #expanded [range_reference.hpp] */ #include /* #expanded [constants.hpp] */ #include namespace lib {enum class comp : std::int8_t {equal_to,not_equal_to,equals = equal_to,eq = equal_to,under,over,under_or,over_or,less = under,more = over,less_than = under,more_than = over,not_less_than = over_or,not_more_than = under_or,leq = under_or,geq = over_or};enum class interval : std::int8_t {right_open,left_open,open,closed,};} /* [constants.hpp] */ namespace lib {namespace internal {template struct range_reference {using size_type = typename Super::size_type;using iterator = typename Super::iterator;protected:const Super *const super;const size_type _begin, _end;range_reference(const Super *const super, const size_type begin, const size_type end) : super(super), _begin(begin), _end(end) {}public:inline iterator begin() const { return std::next(super->begin(), this->_begin); }inline iterator end() const { return std::next(super->begin(), this->_end); }inline size_type size() const { return this->_end - this->_begin; }protected:inline range_reference sub_range(size_type l, size_type r) const {l = this->super->_positivize_index(l), r = this->super->_positivize_index(r);dev_assert(0 <= l and l <= r and r <= this->size());return range_reference(this->super, this->_begin + l, this->_begin + r);}public:templateinline range_reference range(const size_type l, const size_type r) const {if constexpr(rng == lib::interval::right_open) return this->sub_range(l, r);if constexpr(rng == lib::interval::left_open) return this->sub_range(l+1, r+1);if constexpr(rng == lib::interval::open) return this->sub_range(l+1, r);if constexpr(rng == lib::interval::closed) return this->sub_range(l, r+1);}inline range_reference range() const { return range_reference(this->_begin, this->_end); }inline range_reference operator()(const size_type l, const size_type r) const { return this->sub_range(l, r); }inline range_reference subseq(const size_type p, const size_type c) const { return this->sub_range(p, p+c); }inline range_reference subseq(const size_type p) const { return this->sub_range(p, this->size()); }};}} /* [range_reference.hpp] */ /* #expanded [bit_vector.hpp] */ #include #include #include #include namespace lib {struct bit_vector {using size_type = internal::size_t;private:static constexpr size_type w = 64;std::vector _block;std::vector _count;size_type _n, _zeros;public:bit_vector(const size_type _n = 0) { this->init(_n); }template explicit bit_vector(const I first, const I last) : bit_vector(std::distance(first, last)) {size_type pos = 0;for(auto itr=first; itr != last; ++pos, ++itr) if(*itr) this->set(pos);}template bit_vector(const std::initializer_list& init_list) : bit_vector(std::begin(init_list), std::end(init_list)) {}inline size_type size() const { return this->_n; }inline size_type zeros() const { return this->_zeros; }inline size_type ones() const { return this->_n - this->_zeros; }inline void set(const size_type k) { this->_block[k / w] |= 1LL << (k % w); }inline bool get(const size_type k) const { return std::uint32_t(this->_block[k / w] >> (k % w)) & 1U; }__attribute__((optimize("O3", "unroll-loops"))) void init(const int _n) {this->_n = this->_zeros = _n;this->_block.resize(_n / w + 1, 0);this->_count.resize(this->_block.size(), 0);}__attribute__((target("popcnt"))) void build() {for(auto k = 1UL; k < this->_block.size(); ++k) this->_count[k] = this->_count[k-1] + _mm_popcnt_u64(this->_block[k-1]);this->_zeros = this->rank0(this->_n);}__attribute__((target("bmi2,popcnt"))) inline size_type rank1(const size_type k) const {return this->_count[k / w] + _mm_popcnt_u64(_bzhi_u64(this->_block[k / w], k % w));}inline size_type rank0(size_type k) const { return k - this->rank1(k); }inline size_type rank(const bool bit, const size_type k) const {return bit ? this->rank1(k) : this->rank0(k);}__attribute__((target("bmi2,popcnt"))) inline size_type select(const bool bit, const size_type rank) const {if (!bit and rank > this->zeros()) { return this->_n + 1; }if (bit and rank > this->ones()) { return this->_n + 1; }size_type block_pos = 0;{size_type ng = -1, ok = this->_count.size();while(ok - ng > 1) {size_type mid = (ng + ok) / 2;size_type cnt = this->_count[mid];if(!bit) cnt = mid * w - cnt;(cnt >= rank ? ok : ng) = mid;}block_pos = ok;}const size_type base_index = (block_pos - 1) * w;const size_type count = this->_count[block_pos - 1];const std::uint64_t block = this->_block[block_pos - 1];size_type ng = -1, ok = w;while(ok - ng > 1) {const size_type mid = (ok + ng) / 2;size_type r = count + _mm_popcnt_u64(_bzhi_u64(block, mid));if(!bit) r = base_index + mid - r;(r >= rank ? ok : ng) = mid;}return base_index + ok;}inline size_type select0(const size_type k) const { return this->select(0, k); }inline size_type select1(const size_type k) const { return this->select(1, k); }struct iterator : virtual internal::container_iterator_interface {iterator(const bit_vector *const ref, const size_type pos) : internal::container_iterator_interface(ref, pos) {}inline bool operator*() const override { return this->ref()->get(this->pos()); }};inline iterator begin() const { return iterator(this, 0); }inline iterator end() const { return iterator(this, this->size()); }};} /* [bit_vector.hpp] */ /* #expanded [compression.hpp] */ #include #include #include #include namespace lib {template>struct compression : container {using size_type = internal::size_t;protected:std::vector values;public:explicit compression() {}template compression(const I first, const I last) {this->values.assign(first, last);std::sort(this->values.begin(), this->values.end());this->values.erase(std::unique(this->values.begin(), this->values.end()), this->values.end());this->resize(std::distance(first, last));for(auto itr=std::begin(*this),val=this->values.begin(),e=first; e!=last; ++itr,++val,++e) {*itr = this->rank(*e);}}inline size_type rank(const T& val) const {return std::distance(this->values.begin(), std::lower_bound(this->values.begin(), this->values.end(), val));}inline T val() const { return this->values[val]; }inline T operator()(const internal::size_t val) const { return this->values[val]; }};} /* [compression.hpp] */ namespace lib {namespace internal {namespace wavelet_matrix_lib {template struct base {using size_type = internal::size_t;private:size_type _n, _bits;std::vector _index;std::vector> _sum;dict_type _first_pos;T _max = 0;public:base() {}template base(const I first, const I last) { this->build(first, last); }template base(const std::initializer_list& init_list) : base(ALL(init_list)) {}inline size_type size() const { return this->_n; }inline size_type bits() const { return this->_bits; }template __attribute__((optimize("O3"))) void build(const I first, const I last) {this->_n = std::distance(first, last);this->_max = first == last ? -1 : *std::max_element(first, last);this->_bits = atcoder::internal::ceil_pow2(this->_max + 1);this->_index.assign(this->_bits, this->_n);std::vector bit(first, last), nxt(this->_n);this->_sum.assign(this->_bits+1, std::vector(this->_n+1));{size_type i = 0;for(auto itr=first; itr!=last; ++i, ++itr) {this->_sum[this->_bits][i+1] = this->_sum[this->_bits][i] + *itr;}}REPD(h, this->_bits) {std::vector vals;for(size_type i = 0; i < this->_n; ++i) {if((bit[i] >> h) & 1) this->_index[h].set(i);}this->_index[h].build();std::array::iterator,2> itrs{ std::begin(nxt), std::next(std::begin(nxt), this->_index[h].zeros()) };for(size_type i=0; i_n; ++i) *itrs[this->_index[h].get(i)]++ = bit[i];REP(i, this->_n) this->_sum[h][i+1] = this->_sum[h][i] + nxt[i];std::swap(bit, nxt);}REPD(i, this->_n) this->_first_pos[bit[i]] = i;}protected:inline T get(const size_type k) const { return this->_sum[this->_bits][k+1] - this->_sum[this->_bits][k]; }size_type select(const size_type v, const size_type rank) const {if (v > this->_max) return this->_n + 1;if (this->_first_pos.count(v) == 0) return this->_n + 1;size_type pos = this->_first_pos.at(v) + rank + 1;REP(h, this->_bits) {const bool bit = (v >> h) & 1;if(bit) pos -= this->_index[h].zeros();pos = this->_index[h].select(bit, pos);}return pos - 1;}inline T kth_smallest(size_type l, size_type r, size_type k) const {T val = 0;for(size_type h = this->_bits - 1; h >= 0; --h) {size_type l0 = this->_index[h].rank0(l), r0 = this->_index[h].rank0(r);if(k < r0 - l0) {l = l0, r = r0;}else {k -= r0 - l0;val |= T{1} << h;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;}}return val;}inline size_type kth_smallest_index(size_type l, size_type r, size_type k) const {T val = 0;for(size_type h = this->_bits - 1; h >= 0; --h) {size_type l0 = this->_index[h].rank0(l), r0 = this->_index[h].rank0(r);if(k < r0 - l0) {l = l0, r = r0;}else {k -= r0 - l0;val |= T{1} << h;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;}}size_type left = 0;REPD(h, this->_bits) {const bool bit = (val >> h) & 1;left = this->_index[h].rank(bit, left);if(bit) left += this->_index[h].zeros();}return this->select(val, l + k - left);}inline T kth_largest(const size_type l, const size_type r, const size_type k) const {return this->kth_smallest(l, r, r-l-k-1);}inline size_type kth_largest_index(const size_type l, const size_type r, const size_type k) const {return this->kth_smallest_index(l, r, r-l-k-1);}inline std::pair succ0(const size_type l, const size_type r, const size_type h) const {return std::make_pair(this->_index[h].rank0(l), this->_index[h].rank0(r));}inline std::pair succ1(const size_type l, const size_type r, const size_type h) const {size_type l0 = this->_index[h].rank0(l);size_type r0 = this->_index[h].rank0(r);size_type vals = this->_index[h].zeros();return std::make_pair(l + vals - l0, r + vals - r0);}T sum_in_range(const size_type l, const size_type r, const T& x, const T& y, const T& cur, const size_type bit) const {if(l == r) return 0;if(bit == -1) {if(x <= cur and cur < y) return cur * (r - l);return 0;}const T& nxt = (T{1} << bit) | cur;const T& ones = ((T{1} << bit) - 1) | nxt;if(ones < x or y <= cur) return 0;if(x <= cur and ones < y) return this->_sum[bit+1][r] - this->_sum[bit+1][l];const size_type l0 = this->_index[bit].rank0(l), r0 = this->_index[bit].rank0(r);const size_type l1 = l - l0, r1 = r - r0;return this->sum_in_range(l0, r0, x, y, cur, bit - 1) + this->sum_in_range(this->_index[bit].zeros()+l1, this->_index[bit].zeros()+r1, x, y, nxt, bit - 1);}inline T sum_in_range(const size_type l, const size_type r, const T& x, const T& y) const {return this->sum_in_range(l, r, x, y, 0, this->_bits-1);}inline T sum_under(const size_type l, const size_type r, const T& v) const {return this->sum_in_range(l, r, 0, v);}inline T sum_over(const size_type l, const size_type r, const T& v) const {return this->sum_in_range(l, r, v+1, std::numeric_limits::max());}inline T sum_under_or(const size_type l, const size_type r, const T& v) const {return this->sum_in_range(l, r, 0, v+1);}inline T sum_over_or(const size_type l, const size_type r, const T& v) const {return this->sum_in_range(l, r, v, std::numeric_limits::max());}inline T sum(const size_type l, const size_type r) const {return this->_sum[this->_bits][r] - this->_sum[this->_bits][l];}inline size_type count_under(size_type l, size_type r, const T& y) const {if(y >= (T{1} << this->_bits)) return r - l;size_type res = 0;REPD(h, this->_bits) {bool f = (y >> h) & 1;size_type l0 = this->_index[h].rank0(l), r0 = this->_index[h].rank0(r);if(f) {res += r0 - l0;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;} else {l = l0;r = r0;}}return res;}inline size_type count_in_range(const size_type l, const size_type r, const T& x, const T& y) const {return this->count_under(l, r, y) - this->count_under(l, r, x);}inline size_type count_under_or(size_type l, size_type r, const T& v) const {return this->count_under(l, r, v+1);}inline size_type count_over(size_type l, size_type r, const T& v) const {return this->count_over_or(l, r, v+1);}inline size_type count_over_or(size_type l, size_type r, const T& v) const {return r - l - this->count_under(l, r, v);}inline size_type count_equal_to(const size_type l, const size_type r, const T& v) const {return this->count_under(l, r, v+1) - this->count_under(l, r, v);}inline std::optional next_value(const size_type l, const size_type r, const T& v, const size_type k) const {size_type cnt = this->count_under(l, r, v);return cnt + k >= r - l ? std::optional{} : std::optional(this->kth_smallest(l, r, cnt + k));}inline std::optional prev_value(const size_type l, const size_type r, const T& v, const size_type k) const {size_type cnt = this->count_under(l, r, v);return cnt - k < 0 ? std::optional{} : std::optional(this->kth_smallest(l, r, cnt - k));}};}}template> struct compressed_wavelet_matrix;template>struct wavelet_matrix : internal::wavelet_matrix_lib::base {using compressed = compressed_wavelet_matrix;private:using base = typename internal::wavelet_matrix_lib::base;public:using value_type = T;using size_type = typename base::size_type;protected:inline void _validate_index_in_right_open([[maybe_unused]] const size_type p) const {dev_assert(0 <= p and p < this->size());}inline void _validate_index_in_closed([[maybe_unused]] const size_type p) const {dev_assert(0 <= p and p <= this->size());}inline void _validate_rigth_open_interval([[maybe_unused]] const size_type l, [[maybe_unused]] const size_type r) const {dev_assert(0 <= l and l <= r and r <= this->size());}inline size_type _positivize_index(const size_type p) const {return p < 0 ? this->size() + p : p;}public:using base::base;inline T get(size_type k) const {k = this->_positivize_index(k);this->_validate_index_in_right_open(k);return this->base::get(k);}inline T operator[](const size_type k) const { return this->get(k); }struct iterator;struct range_reference;templateinline range_reference range(const size_type l, const size_type r) const {if constexpr(rng == lib::interval::right_open) return range_reference(this, l, r);if constexpr(rng == lib::interval::left_open) return range_reference(this, l+1, r+1);if constexpr(rng == lib::interval::open) return range_reference(this, l+1, r);if constexpr(rng == lib::interval::closed) return range_reference(this, l, r+1);}inline range_reference range() const { return range_reference(this, 0, this->size()); }inline range_reference operator()(const size_type l, const size_type r) const { return range_reference(this, l, r); }inline range_reference subseq(const size_type p, const size_type c) const { return range_reference(this, p, p+c); }inline range_reference subseq(const size_type p) const { return range_reference(this, p, this->size()); }struct range_reference : internal::range_reference {range_reference(const wavelet_matrix *const super, const size_type l, const size_type r): internal::range_reference(super, super->_positivize_index(l), super->_positivize_index(r)){this->super->_validate_rigth_open_interval(this->_begin, this->_end);}inline T get(const size_type k) const {k = this->super->_positivize_index(k);dev_assert(0 <= k and k < this->size());return this->super->get(this->_begin + k);}inline T operator[](const size_type k) const { return this->get(k); }inline T kth_smallest(const size_type k) const {dev_assert(0 <= k and k < this->size());return this->super->base::kth_smallest(this->_begin, this->_end, k);}inline auto kth_smallest_element(const size_type k) const {dev_assert(0 <= k and k < this->size());return std::next(this->super->begin(), this->super->base::kth_smallest_index(this->_begin, this->_end, k));}inline T kth_largest(const size_type k) const {dev_assert(0 <= k and k < this->size());return this->super->base::kth_largest(this->_begin, this->_end, k);}inline auto kth_largest_element(const size_type k) const {dev_assert(0 <= k and k < this->size());return std::next(this->super->begin(), this->super->base::kth_largest_index(this->_begin, this->_end, k));}inline T min() const { return this->kth_smallest(0); }inline T max() const { return this->kth_largest(0); }inline T median() const { return this->kth_smallest(this->size() / 2); }inline T sum_in_range(const T& x, const T& y) const { return this->super->base::sum_in_range(this->_begin, this->_end, x, y); }inline T sum_under(const T& v) const { return this->super->base::sum_under(this->_begin, this->_end, v); }inline T sum_over(const T& v) const { return this->super->base::sum_over(this->_begin, this->_end, v); }inline T sum_under_or(const T& v) const { return this->super->base::sum_under_or(this->_begin, this->_end, v); }inline T sum_over_or(const T& v) const { return this->super->base::sum_over_or(this->_begin, this->_end, v); }inline T sum(const T& x, const T& y) const { return this->super->base::sum_in_range(this->_begin, this->_end, x, y); }inline T sum() const { return this->super->base::sum(this->_begin, this->_end); }templateinline size_type sum(const T& v) const {if constexpr(com == comp::under) return this->sum_under(v);if constexpr(com == comp::over) return this->sum_over(v);if constexpr(com == comp::under_or) return this->sum_under_or(v);if constexpr(com == comp::over_or) return this->sum_over_or(v);assert(false);}inline size_type count_in_range(const T& x, const T& y) const { return this->super->base::count_in_range(this->_begin, this->_end, x, y); }inline size_type count_under(const T& v) const { return this->super->base::count_under(this->_begin, this->_end, v); }inline size_type count_over(const T& v) const { return this->super->base::count_over(this->_begin, this->_end, v); }inline size_type count_under_or(const T& v) const { return this->super->base::count_under_or(this->_begin, this->_end, v); }inline size_type count_over_or(const T& v) const { return this->super->base::count_over_or(this->_begin, this->_end, v); }templateinline size_type count(const T& v) const {if constexpr(com == comp::eq) return this->super->count_equal_to(this->_begin, this->_end, v);if constexpr(com == comp::under) return this->count_under(v);if constexpr(com == comp::over) return this->count_over(v);if constexpr(com == comp::under_or) return this->count_under_or(v);if constexpr(com == comp::over_or) return this->count_over_or(v);assert(false);}inline std::optional next_value(const T& v, const size_type k = 0) const { return this->super->base::next_value(this->_begin, this->_end, v, k); }inline std::optional prev_value(const T& v, const size_type k = 1) const { return this->super->base::prev_value(this->_begin, this->_end, v, k); }};inline T kth_smallest(const size_type k) const { return this->range().kth_smallest(k); }inline T kth_smallest_element(const size_type k) const { return this->range().kth_smallest_element(k); }inline T kth_largest(const size_type k) const { return this->range().kth_largest(k); }inline T kth_largest_element(const size_type k) const { return this->range().kth_largest_element(k); }inline T min() const { return this->range().kth_smallest(0); }inline T max() const { return this->range().kth_largest(0); }inline T median() const { return this->range().median(); }inline T sum_in_range(const T& x, const T& y) const { return this->range().sum_in_range(x, y); }inline T sum_under(const T& v) const { return this->range().sum_under(v); }inline T sum_over(const T& v) const { return this->range().sum_over(v); }inline T sum_under_or(const T& v) const { return this->range().sum_under_or(v); }inline T sum_over_or(const T& v) const { return this->range().sum_over_or(v); }inline T sum(const T& x, const T& y) const { return this->range().sum_in_range(x, y); }inline T sum() const { return this->range().sum(); }templateinline size_type sum(const T& v) const { return this->range().template sum(v); }inline size_type count_in_range(const T& x, const T& y) const { return this->range().count_in_range(x, y); }inline size_type count_under(const T& v) const { return this->range().count_under(v); }inline size_type count_over(const T& v) const { return this->range().count_over(v); }inline size_type count_under_or(const T& v) const { return this->range().count_under_or(v); }inline size_type count_over_or(const T& v) const { return this->range().count_over_or(v); }inline size_type count(const T& x, const T& y) const { return this->range().count(x, y); }templateinline size_type count(const T& v) const { return this->range().template count(v); }inline std::optional next_value(const T& v, const size_type k = 0) const { return this->range().next_value(v, k); }inline std::optional prev_value(const T& v, const size_type k = 1) const { return this->range().prev_value(v, k); }struct iterator : virtual internal::container_iterator_interface {iterator(const wavelet_matrix *const ref, const size_type pos) : internal::container_iterator_interface(ref, pos) {}inline T operator*() const override { return this->ref()->get(this->pos()); }};inline iterator begin() const { return iterator(this, 0); }inline iterator end() const { return iterator(this, this->size()); }};templatestruct compressed_wavelet_matrix : protected wavelet_matrix::size_type,dict_type> {protected:using core = wavelet_matrix::size_type,dict_type>;compression compressed;public:using size_type = typename core::size_type;template compressed_wavelet_matrix(const I first, const I last) { this->build(first, last); }template void build(const I first, const I last) {this->compressed = compression(first, last);this->core::build(ALL(this->compressed));}inline T get(const size_type k) const { return this->compressed(this->core::get(k)); }inline size_type operator[](const size_type k) const { return this->core::get(k); }struct iterator;struct range_reference;templateinline range_reference range(const size_type l, const size_type r) const {if constexpr(rng == lib::interval::right_open) return range_reference(this, l, r);if constexpr(rng == lib::interval::left_open) return range_reference(this, l+1, r+1);if constexpr(rng == lib::interval::open) return range_reference(this, l+1, r);if constexpr(rng == lib::interval::closed) return range_reference(this, l, r+1);}inline range_reference range() const { return range_reference(this, 0, this->size()); }inline range_reference operator()(const size_type l, const size_type r) const { return range_reference(this, l, r); }inline range_reference subseq(const size_type p, const size_type c) const { return range_reference(this, p, p+c); }inline range_reference subseq(const size_type p) const { return range_reference(this, p, this->size()); }struct range_reference : internal::range_reference {range_reference(const compressed_wavelet_matrix *const super, const size_type l, const size_type r): internal::range_reference(super, super->_positivize_index(l), super->_positivize_index(r)){this->super->_validate_rigth_open_interval(this->_begin, this->_end);}private:inline auto _range() const { return this->super->core::range(this->_begin, this->_end); }public:inline T get(const size_type k) const { return this->super->compressed(this->_range().get(k)); }inline T operator[](const size_type k) const { return this->get(k); }inline T kth_smallest(const size_type k) const { return this->super->compressed(this->_range().kth_smallest(k)); }inline auto kth_smallest_element(const size_type k) const {return std::next(this->super->begin(), std::distance(this->super->core::begin(), this->_range().kth_smallest_element(k)));}inline T kth_largest(const size_type k) const { return this->super->compressed(this->_range().kth_largest(k));}inline auto kth_largest_element(const size_type k) const {return std::next(this->super->begin(), std::distance(this->super->core::begin(), this->_range().kth_largest_element(k)));}inline T min() const { return this->kth_smallest(0); }inline T max() const { return this->kth_largest(0); }inline T median() const { return this->kth_smallest(this->size() / 2); }inline size_type count_in_range(const T& x, const T& y) const {return this->_range().count_in_range(this->super->compressed.rank(x), this->super->compressed.rank(y));}inline size_type count_under(const T& v) const { return this->_range().count_under(this->super->compressed.rank(v)); }inline size_type count_over(const T& v) const { return this->_range().count_over(this->super->compressed.rank(v)); }inline size_type count_under_or(const T& v) const { return this->_range().count_under_or(this->super->compressed.rank(v)); }inline size_type count_over_or(const T& v) const { return this->_range().count_over_or(this->super->compressed.rank(v)); }templateinline size_type count(const T& v) const { return this->_range().template count(this->super->compressed.rank(v)); }inline std::optional next_value(const T& v, const size_type k = 0) const {std::optional res = this->_range().next_value(this->super->compressed.rank(v), k);if(res.has_value()) return this->super->compressed(res.value());return {};}inline std::optional prev_value(const T& v, const size_type k = 1) const {std::optional res = this->_range().prev_value(this->super->compressed.rank(v), k);if(res.has_value()) return this->super->compressed(res.value());return {};}};inline T kth_smallest(const size_type k) const { return this->range().kth_smallest(k); }inline auto kth_smallest_element(const size_type k) const { return this->range().kth_smallest_element(k); }inline T kth_largest(const size_type k) const { return this->range().kth_largest(k); }inline auto kth_largest_element(const size_type k) const { return this->range().kth_largest_element(k); }inline T min() const { return this->range().kth_smallest(0); }inline T max() const { return this->range().kth_largest(0); }inline T median() const { return this->range().median(); }inline size_type count_in_range(const T& x, const T& y) const { return this->range().count_in_range(x, y); }inline size_type count_under(const T& v) const { return this->range().count_under(v); }inline size_type count_over(const T& v) const { return this->range().count_over(v); }inline size_type count_under_or(const T& v) const { return this->range().count_under_or(v); }inline size_type count_over_or(const T& v) const { return this->range().count_over_or(v); }template inline size_type count(const T& v) const { return this->range().template count(v); }inline std::optional next_value(const T& v, const size_type k = 0) const { return this->range().next_value(v, k); }inline std::optional prev_value(const T& v, const size_type k = 1) const { return this->range().prev_value(v, k); }struct iterator : virtual internal::container_iterator_interface {iterator(const compressed_wavelet_matrix *const ref, const size_type pos) : internal::container_iterator_interface(ref, pos) {}inline T operator*() const override { return this->ref()->get(this->pos()); }};inline iterator begin() const { return iterator(this, 0); }inline iterator end() const { return iterator(this, this->size()); }};} /* [wavelet_matrix.hpp] */ signed main() { int n, k; std::cin >> n >> k; std::vector a(n); ITRR(v, a) std::cin >> v; lib::wavelet_matrix data(ALL(a)); ll ans = LONG_LONG_MAX; FOR(i, 0, n-k) { auto range = data.subseq(i, k); debug(range); ll med = range.median(); ll costl = med * range.count_under(med) - range.sum_under(med); ll costr = range.sum_over_or(med) - med * range.count_over_or(med); chmin(ans, costl + costr); } print(ans); }