#include <bits/stdc++.h>
#include "plants.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define N 200005
#define PB push_back
#define sz(x) int(x.size())
#define P 31
#define F first
#define M ll(1e9 + 7)
#define S second
#define all(x) x.begin(), x.end()
//#define endl '\n'
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
//typedef tree<int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll mlt(ll a, ll b) {return (a * b) % M;}
ll sm(ll a, ll b) {return (a + b) % M;}
int id, K, h[N];
array <int, 2> t[N * 4];
int psh[N * 4], n, val[N];
pair <int, int> nxt[N];
vector <pair <int, int> > gt[N];
vector <int> a;
set <int> g[N];
void Push(int v, int tl, int tr)
{
t[v][0] += psh[v];
t[v][0] = max(t[v][0], 0);
if (tl != tr)
{
psh[v + v] += psh[v];
psh[v + v + 1] += psh[v];
}
psh[v] = 0;
}
void com(int v)
{
if (t[v + v][0] < t[v + v + 1][0]) t[v] = t[v + v];
else t[v] = t[v + v + 1];
}
void bld(int v, int tl, int tr)
{
if (tl == tr) t[v] = {a[tl], tl};
else
{
int md = (tl + tr) >> 1;
bld(v + v, tl, md);
bld(v + v + 1, md + 1, tr);
com(v);
}
}
void upd(int v, int tl, int tr, int ps)
{
Push(v, tl, tr);
if (tr < ps || ps < tl) return;
if (tl == tr) t[v] = {int(1e9), tl};
else
{
int md = (tl + tr) >> 1;
upd(v + v, tl, md, ps);
upd(v + v + 1, md + 1, tr, ps);
com(v);
}
}
void upd(int v, int tl, int tr, int l, int r)
{
Push(v, tl, tr);
if (tr < l || r < tl || l > r || tl > tr) return;
if (l <= tl && tr <= r) {psh[v]--; Push(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd(v + v, tl, md, l, r);
upd(v + v + 1, md + 1, tr, l, r);
com(v);
}
void dfs(int v)
{
pair <int, int> pt;
pt.F = id++;
for (auto it : g[v])
dfs(it);
pt.S = id++;
gt[v].PB(pt);
}
void init(int k, vector<int> r)
{
K = k;
n = sz(r);
if (k == 2)
{
set <int> se; se.clear();
for (int i = 0; i < sz(r); i++) se.insert(i);
for (int i = 0; i < sz(r); i++)
{
int nxt = (i + 1) % sz(r);
if (r[i] == 1) {g[nxt].insert(i); se.erase(i);}
else {g[i].insert(nxt);se.erase(nxt);}
}
for (auto it : se) dfs(it);
return;
}
a = r;
bld(1, 0, n - 1);
int cur = n;
while (cur > 0)
{
vector <int> gr; gr.clear();
while (t[1][0] == 0)
{
gr.PB(t[1][1]);
upd(1, 0, n - 1, t[1][1]);
}
sort(all(gr));
set <pair <int, int> > se; se.clear();
set <int> st; st.clear();
for (int i = 0; i < sz(gr); i++)
{
int x = gr[i];
st.insert(x);
if (i == 0) {nxt[x].F = gr.back(); val[x] = gr[i] + n - gr.back();}
else {nxt[x].F = gr[i - 1]; val[x] = gr[i] - gr[i - 1];}
if (i + 1 == sz(gr)) nxt[x].S = gr[0];
else nxt[x].S = gr[i + 1];
se.insert({val[x], x});
}
while (sz(se) > 0)
{
// cout << "Saved: "; for (auto it : se) cout << it.S << " "; cout << endl;
int glob = cur;
vector <int> pr; pr.clear();
while (sz(se) > 0 && (sz(pr) == 0))
{
int ps = (*se.rbegin()).S;
se.erase(*se.rbegin());
st.erase(ps);
pr.PB(ps);
h[ps] = glob;
cur--;
}
if (sz(se) > 0 && (*se.rbegin()).F >= K) exit(0);
for (int i = 0; i < sz(pr); i++)
{
// while (sz(se) > 0 && ((*se.rbegin()).F >= K || sz(pr) == 0))
// {
// int ps = (*se.rbegin()).S;
//
// se.erase(*se.rbegin());
//
// st.erase(ps);
//
// pr.PB(ps);
//
// h[ps] = glob;
//
// cur--;
// }
int ps = pr[i];
// cout << "maked: " << ps << endl;
if (sz(st) != 0)
{
nxt[nxt[ps].F].S = nxt[ps].S;
nxt[nxt[ps].S].F = nxt[ps].F;
int l = nxt[ps].F, r = nxt[ps].S;
bool f = 0;
if (se.find({val[r], r}) != se.end()) {f = 1; se.erase({val[r], r});}
if (l < r) val[r] = r - l;
else val[r] = n - l + r;
if (f) se.insert({val[r], r});
}
upd(1, 0, n - 1, max(0, ps - k + 1), ps - 1);
if (ps - k + 1 < 0) upd(1, 0, n - 1, n - abs(ps - k + 1), n - 1);
while (t[1][0] == 0)
{
int ps = t[1][1];
upd(1, 0, n - 1, ps);
if (sz(st) == 0)
{
nxt[ps].F = nxt[ps].S = ps;
val[ps] = 0;
}
else
{
auto it = st.upper_bound(ps);
int l, r;
if (it == st.end())
{
r = *st.begin();
it--;
l = *it;
}
else if (it == st.begin())
{
r = *it;
l = *st.rbegin();
}
else
{
r = *it;
it--;
l = *it;
}
se.erase({val[r], r});
nxt[r].F = nxt[l].S = ps;
nxt[ps].F = l; nxt[ps].S = r;
if (l < ps) val[ps] = ps - l;
else val[ps] = n - l + ps;
if (ps < r) val[r] = r - ps;
else val[r] = n - ps + r;
se.insert({val[r], r});
}
st.insert(ps);
se.insert({val[ps], ps});
// cout << val[ps] << " " << ps << endl;
}
}
}
}
return;
}
int compare_plants(int x, int y)
{
if (K == 2)
{
for (auto it : gt[x])
for (auto itr : gt[y])
if (it.F <= itr.F && itr.S <= it.S) return 1;
else if (itr.F <= it.F && it.S <= itr.S) return -1;
return 0;
}
if (h[x] > h[y]) return 1;
if (h[x] == h[y]) return 0;
return -1;
}
//int main()
//{
//// freopen("help.in", "r", stdin); freopen("help.out", "w", stdout);
//
// ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
// init(4, {0, 1, 3, 3, 3, 2, 3, 1, 0});
//
// for (int i = 0; i < 9; i++) cout << h[i] << " ";
//}
