#include <bits/stdc++.h>
/* #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 <utility>
constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };template<class T1, class T2> inline auto mod(T1 x, T2 r) { return (x%r+r)%r; }template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return (a<b ? a=b, true : false); }template<class T1, class T2> 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<i##_length; ++i)
#define REPF(i,l,r) for(auto i=(l), i##_last=(r); i!=i##_last; ++i)
#define REPIS(i,l,r,s) for(auto i=(l), i##_last=(r); i!=i##_last; i+=(s))
#define REPR(i,n) for(auto i=(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 <iostream>
#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<debug>
#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 <atcoder/modint>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
/* #expanded [resolving_rank.hpp] */
namespace lib {namespace internal {template<int P> struct resolving_rank : resolving_rank<P-1> {};template<> struct resolving_rank<0> {};}}
/* [resolving_rank.hpp] */
template<class source = std::istream>struct input_adapter {private:template<class T>auto _set(lib::internal::resolving_rank<3>, T *const val) -> decltype(std::declval<source>() >> *val, 0) {*this->in >> *val;return 0;}template<class T>auto _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;}template<class T>auto _set(lib::internal::resolving_rank<1>, T *const val) -> decltype(val->first, val->second, 0) {(*this)(&*val);return 0;}template<class T>auto _set(lib::internal::resolving_rank<0>, T *const val) -> std::enable_if_t<atcoder::internal::is_modint<T>::value,int> {long long v; std::cin >> v;*val = { v };return 0;}protected:template<class T>source *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<class T> inline input_adapter& operator>>(T &s) {this->set(&s);return *this;}template<class T> inline T one() {T val; *this >> val;return val;}template<class T> inline void operator()(T*const val) {*this >> *val;}template<class T, class ...Args> inline void operator()(T*const head, Args*const ...tail) {*this >> *head;(*this)(tail...);}template<class I, class = typename I::value_type> inline void operator()(I first, I last) {for(I itr=first; itr!=last; ++itr) *this >> *itr;}template<class F, class S> inline void operator()(std::pair<F,S> *const p) {(*this)(&p->first, &p->second);}};
/* [input.hpp] */
/* #expanded [output.hpp] */
#include <iostream>
#include <string>
#include <vector>

template<class destination = std::ostream, class Terminator = std::string, class Separator = std::string>struct output_adapter {private:template<class T>auto _put(lib::internal::resolving_rank<2>, const T &val) -> decltype(std::declval<destination>() << val, 0) {*this->out << val;return 0;}template<class T>auto _put(lib::internal::resolving_rank<1>, const T &val) -> decltype(val.val(), 0) {*this->out << val.val();return 0;}template<class T>auto _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:template<class T>destination *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<char_type,std::char_traits<char_type>>;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<class T> inline output_adapter& operator<<(const T &s) {this->put(s);return *this;}template<class T = std::string> inline void operator()(const T &val = "") {*this << val << this->endline;}template<class T, class ...Args> inline void operator()(const T &head, const Args& ...tail) {*this << head << this->separator;(*this)(tail...);}template<class I, class = typename I::iterator_category> 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<class T> inline void operator()(const std::initializer_list<T> vals) {std::vector wrapped(vals.begin(), vals.end());(*this)(wrapped.begin(), wrapped.end());}template<class F, class S> inline void operator()(const std::pair<F,S> &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 <cstdint>
#include <utility>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <optional>
#include <limits>
#include <atcoder/internal_bit>

/* #expanded [dev_assert.hpp] */
#ifdef LOCAL_JUDGE
#include <cassert>
#define dev_assert(...) assert(__VA_ARGS__)
#else
#define dev_assert(...) ({ ; })
#endif
/* [dev_assert.hpp] */
/* #expanded [types.hpp] */
#include <cstdint>
namespace lib {namespace internal {using size_t = std::int32_t;}}
/* [types.hpp] */
/* #expanded [iterator.hpp] */
#include <iterator>

namespace lib {namespace internal {template<class T>struct 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;};template<class T>struct bidirectiona_Iterator_interface : iterator_interface<T> {using iterator_category = std::bidirectional_iterator_tag;virtual bidirectiona_Iterator_interface& operator++() = 0;virtual bidirectiona_Iterator_interface& operator--() = 0;};template<class T>struct random_access_iterator_base : bidirectiona_Iterator_interface<T> {using iterator_category = std::random_access_iterator_tag;using difference_type = typename bidirectiona_Iterator_interface<T>::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;};template<class T, class container>struct container_iterator_interface : public random_access_iterator_base<T> {using difference_type = typename bidirectiona_Iterator_interface<T>::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 [succinct_bit_vector.hpp] */

#include <vector>
#include <cstdint>
#include <immintrin.h>
namespace lib {struct succinct_bit_vector {using size_type = internal::size_t;private:using uint32 = std::uint32_t;using int64 = std::int64_t;using uint64 = std::uint64_t;static constexpr uint32 w = 64;std::vector<uint64> _block;std::vector<uint32> _count;size_type _n, _zeros;public:succinct_bit_vector() {}succinct_bit_vector(const size_type _n) { this->init(_n); }inline size_type size() const { return this->_n; }inline size_type zeros() const { return this->_zeros; }inline void set(size_type i) { this->_block[i / w] |= 1LL << (i % w); }inline bool get(size_type i) const { return uint32(this->_block[i / w] >> (i % 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 i=1UL; i < this->_block.size(); ++i) this->_count[i] = this->_count[i - 1] + _mm_popcnt_u64(this->_block[i - 1]);this->_zeros = this->rank0(this->_n);}__attribute__((target("bmi2,popcnt"))) inline size_type rank1(size_type i) const {return this->_count[i / w] + _mm_popcnt_u64(_bzhi_u64(this->_block[i / w], i % w));}inline size_type rank0(size_type i) const { return i - this->rank1(i); }};}
/* [succinct_bit_vector.hpp] */
/* #expanded [constants.hpp] */
#include <cstdint>
namespace lib {enum class conditions : std::int8_t {equal_to,not_equal_to,equals = equal_to,eq = equal_to,under,over,or_under,or_over,less = under,more = over,less_than = under,more_than = over,not_less_than = or_over,not_more_than = or_under,leq = or_under,geq = or_over};}
/* [constants.hpp] */
namespace lib {namespace internal {namespace wavelet_matrix_lib {template<class T> struct base {using size_type = internal::size_t;private:using int64 = std::int64_t;using uint64 = std::uint64_t;size_type _n, _bits;std::vector<succinct_bit_vector> _index;std::vector<size_type> _first_ones;std::vector<std::vector<T>> _sum;T _max = 0;public:template<class I> base(const I first, const I last) { this->build(first, last); }inline size_type size() const { return this->_n; }inline size_type bits() const { return this->_bits; }template<class I> __attribute__((optimize("O3"))) void build(const I first, const I last) {this->_n = std::distance(first, last);this->_max = first == last ? 0 : *std::max_element(first, last) + 1;this->_bits = atcoder::internal::ceil_pow2(this->_max);this->_index.assign(this->_bits, this->_n);this->_first_ones.assign(this->_bits, this->_n);std::vector<T> depth(first, last), nxt(this->_n);this->_sum.assign(this->_bits+1, std::vector<T>(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;}}for(size_type h = this->_bits - 1; h >= 0; --h) {std::vector<size_type> vals;for(size_type i = 0; i < this->_n; ++i) {if((depth[i] >> h) & 1) this->_index[h].set(i);}this->_index[h].build();this->_first_ones[h] = this->_index[h].zeros();std::array<typename std::vector<T>::iterator,2> itrs{ std::begin(nxt), std::next(std::begin(nxt), this->_index[h].zeros()) };for(size_type i=0; i<this->_n; ++i) *itrs[this->_index[h].get(i)]++ = depth[i];REP(i, nxt.size()) this->_sum[h][i+1] = this->_sum[h][i] + nxt[i];std::swap(depth, nxt);}}protected:T sum(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(l0, r0, x, y, cur, bit - 1) + this->sum(this->_first_ones[bit]+l1, this->_first_ones[bit]+r1, x, y, nxt, bit - 1);}inline T sum(const size_type l, const size_type r, const size_type x, const size_type y) const {return this->sum(l, r, x, y, 0, this->_bits-1);}inline T get(size_type k) const {T res = 0;for(size_type h = this->_bits - 1; h >= 0; --h) {bool f = this->_index[h].get(k);res |= f ? T(1) << h : 0;k = f ? this->_index[h].rank1(k) + this->_index[h].zeros() : this->_index[h].rank0(k);}return res;}inline T kth_smallest(size_type l, size_type r, size_type k) const {T res = 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;res |= (T)1 << h;l += this->_index[h].zeros() - l0;r += this->_index[h].zeros() - r0;}}return res;}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;for(size_type h = this->_bits - 1; h >= 0; --h) {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 std::pair<size_type,size_type> 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<size_type,size_type> 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);}};}}template<class T> struct wavelet_matrix : internal::wavelet_matrix_lib::base<T> {private:using base = typename internal::wavelet_matrix_lib::base<T>;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 void set(const size_type i, const T& x) const { this->base::set(i, x); }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); }inline T min(const size_type l, const size_type r) { return this->kth_smallest(l, r, 0); }inline T min() { return this->kth_smallest(0, this->size(), 0); }inline T max(const size_type l, const size_type r) { return this->kth_largest(l, r, 0); }inline T max() { return this->kth_largest(0, this->size(), 0); }T sum(size_type l, size_type r, const T& x, const T& y) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);return this->base::sum(l, r, x, y);}inline T sum(const size_type l, const size_type r) const {return this->sum(l, r, -1, std::numeric_limits<T>::max());}inline T sum() const { return this->sum(0, this->size()); }inline std::pair<size_type,size_type> succ0(size_type l, size_type r, const size_type h) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);return this->base::succ0(l, r, h);}inline std::pair<size_type,size_type> succ1(size_type l, size_type r, const size_type h) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);return this->base::succ1(l, r, h);}inline size_type count_under(size_type l, size_type r, const T& y) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);return this->base::count_under(l, r, y);}inline size_type count_under(const T& y) const {return this->base::count_under(0, this->size(), y);}inline size_type count_or_over(size_type l, size_type r, const T& x) const {return r - l - this->count_under(l, r, x);}inline size_type count_or_over(const T& x) const {return this->size() - this->count_under(x);}inline size_type count_over(size_type l, size_type r, const T& x) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);return this->base::count_or_over(l, r, x+1);}inline size_type count_over(const T& x) const {return this->base::count_over(0, this->size(), x);}inline size_type count_or_under(size_type l, size_type r, const T& y) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);return this->base::count_under(l, r, y+1);}inline size_type count_or_under(const T& y) const {return this->base::count_or_under(0, this->size(), y);}inline size_type count(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(const T& x, const T& y) const {return this->count_under(y) - this->count_under(x);}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 size_type count_equal_to(const T& v) const {return this->count_under(v+1) - this->count_under(v);}template<conditions cond>inline size_type count(const size_type l, const size_type r, const T& v) const {if constexpr(cond == conditions::eq) return this->count_equal_to(l, r, v);if constexpr(cond == conditions::under) return this->count_under(l, r, v);if constexpr(cond == conditions::over) return this->count_over(l, r, v);if constexpr(cond == conditions::or_under) return this->count_or_under(l, r, v);if constexpr(cond == conditions::or_over) return this->count_or_over(l, r, v);assert(false);}inline T kth_smallest(size_type l, size_type r, const size_type k) const {l = this->_positivize_index(l), r = this->_positivize_index(r);this->_validate_rigth_open_interval(l, r);dev_assert(0 <= k and k < r-l);return this->base::kth_smallest(l, r, k);}inline T kth_smallest(const size_type k) const {dev_assert(0 <= k and k < this->size());return this->base::kth_smallest(0, this->size(), k);}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 T kth_largest(const size_type k) const {return this->kth_smallest(this->size()-k-1);}inline std::optional<T> prev_value(const size_type l, const size_type r, const T& y) const {size_type cnt = this->count_under(l, r, y);return cnt == 0 ? std::optional<T>{} : std::optional<T>(this->kth_smallest(l, r, cnt - 1));}inline std::optional<T> prev_value(const T& y) const {size_type cnt = this->count_under(y);return cnt == 0 ? std::optional<T>{} : std::optional<T>(this->kth_smallest(cnt - 1));}inline std::optional<T> next_value(const size_type l, const size_type r, const T& x) {size_type cnt = this->count_under(l, r, x);return cnt == r - l ? std::optional<T>{} : std::optional<T>(this->kth_smallest(l, r, cnt));}inline std::optional<T> next_value(const T& x) {size_type cnt = this->count_under(x);return cnt == this->size() ? std::optional<T>{} : std::optional<T>(this->kth_smallest(cnt));}struct iterator : virtual internal::container_iterator_interface<T,wavelet_matrix> {iterator(const wavelet_matrix *const ref, const size_type pos) : internal::container_iterator_interface<T,wavelet_matrix>(ref, pos) {}inline value_type 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<ll> a(n); ITRR(v, a) std::cin >> v;
    lib::wavelet_matrix<ll> data(ALL(a));

    ll ans = LONG_LONG_MAX;
    FOR(i, 0, n-k) {
        int l = i, r = i + k;

        ll med = data.kth_smallest(l, r, k/2);

        ll less_cost = med * data.count<lib::conditions::less_than>(l, r, med) - data.sum(l, r, 0, med);
        ll or_over_cost = data.sum(l, r, med, INT_MAX) - med * data.count<lib::conditions::geq>(l, r, med);

        chmin(ans, less_cost + or_over_cost);
    }

    print(ans);
}