#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <array>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <fstream>
#include <iomanip>
#include <istream>
#include <map>
#include <math.h>
#include <numeric>
#include <ostream>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
namespace asl
{
void fin(std::string word)
{
std::cout << word << std::endl;
std::exit(0);
}
} // namespace asl
#include <stdint.h>
#include <experimental/optional>
#define optional std::experimental::optional
namespace asl
{
template <typename T, typename U = T>
class SegmentTree
{
int size;
std::function<void(T &, U &)> _update;
std::function<T(T &, T &)> _merge;
std::function<optional<U>(T &)> _get_lazy;
void push(int p, int l, int r)
{
auto lazy = _get_lazy(ds[p]);
if (lazy)
{
_update(ds[l], *lazy);
_update(ds[r], *lazy);
}
}
void update(int p, int b, int e, int x, int y, U &upd)
{
if (x <= b && e <= y)
{
_update(ds[p], upd);
}
else
{
int m = (b + e) >> 1, l = p + 1, r = p + ((m - b) << 1);
push(p, l, r);
if (x < m)
update(l, b, m, x, y, upd);
if (m < y)
update(r, m, e, x, y, upd);
ds[p] = _merge(ds[l], ds[r]);
}
}
T query(int p, int b, int e, int x, int y)
{
if (x <= b && e <= y)
{
return ds[p];
}
else
{
int m = (b + e) >> 1, l = p + 1, r = p + ((m - b) << 1);
push(p, l, r);
if (x < m)
{
auto le = query(l, b, m, x, y);
if (m < y)
{
auto ri = query(r, m, e, x, y);
return _merge(le, ri);
}
else
{
return le;
}
}
else
{
return query(r, m, e, x, y);
}
}
}
void build(int p, int b, int e, std::function<T(int)> &builder)
{
if (b + 1 == e)
{
ds[p] = builder(b);
}
else
{
int m = (b + e) >> 1, l = p + 1, r = p + ((m - b) << 1);
build(l, b, m, builder);
build(r, m, e, builder);
ds[p] = _merge(ds[l], ds[r]);
}
}
void init(int size,
std::function<void(T &, U &)> update,
std::function<T(T &, T &)> merge,
std::function<optional<U>(T &)> get_lazy)
{
this->size = size;
this->_update = update;
this->_merge = merge;
this->_get_lazy = get_lazy;
this->ds = std::vector<T>(2 * size - 1);
}
public:
std::vector<T> ds;
SegmentTree(
int size,
std::function<void(T &, U &)> update,
std::function<T(T &, T &)> merge = [](T &l, T &r) { return l + r; },
std::function<optional<U>(T &)> get_lazy = [](T &value) { return optional<U>(); })
{
init(size, update, merge, get_lazy);
}
void build(std::function<T(int)> builder)
{
build(0, 0, size, builder);
}
void update(int x, U upd)
{
update(0, 0, size, x, x + 1, upd);
}
void update(int x, int y, U upd)
{
update(0, 0, size, x, y, upd);
}
T query(int x, int y)
{
return query(0, 0, size, x, y);
}
};
} // namespace asl
#include <tuple>
#include <random>
#include <utility>
using namespace std;
using namespace asl;
vector<int> xrank;
struct state
{
int value, left, right, max_diff, index, lazy;
};
void init(int k, vector<int> r)
{
int n = r.size();
xrank.resize(n);
SegmentTree<state, int> st(
n, [&](state &s, int &u) { s.value += u; s.lazy += u; },
[&](state &l, state &r) { state res;
if (l.value < r.value) {
res = l;
res.lazy = 0;
} else if (r.value < l.value) {
res = r;
res.lazy = 0;
} else {
res.value = l.value;
res.left = l.left;
res.right = r.right;
res.max_diff = max({l.max_diff, r.max_diff, r.left - l.right});
res.lazy = 0;
if (l.max_diff == res.max_diff) {
res.index = l.index;
} else if (r.max_diff == res.max_diff) {
res.index = r.index;
} else {
res.index = r.left;
}
}
return res; },
[&](state &s) {
if (s.lazy) {
int value = s.lazy;
s.lazy = 0;
return optional<int>(value);
} else {
return optional<int>();
} });
st.build([&](int p) {
state res = {r[p], p, p, 0, p, 0};
return res;
});
for (int i = 0; i < n; ++i)
{
auto res = st.query(0, n);
int wrap_diff = res.left + n - res.right;
int index = res.index;
if (wrap_diff > res.max_diff)
index = res.left;
xrank[index] = n - i;
st.update(index, +1e6);
if (index >= k - 1)
st.update(index - k + 1, index, -1);
else
{
if (index)
st.update(0, index, -1);
st.update(n + index - (k - 1), n, -1);
}
}
}
int compare_plants(int a, int b)
{
return xrank[a] > xrank[b] ? +1 : -1;
}
