#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, 3> t[N * 4];
int psh[N * 4], psp[N * 4], n;
vector <pair <int, int> > gt[N];
vector <int> a;
set <int> g[N];
void updater(int v, int ps, int l, int r)
{
if (psp[v] == -1) psp[v] = ps;
else
{
int len1, len2;
if (r < psp[v]) len1 = n - psp[v] + l;
else l - psp[v];
if (r < ps) len2 = n - ps + l;
else l - ps;
if (len2 > len1) psp[v] = ps;
}
}
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;
if (psp[v] == -1) return;
if (tl != tr)
{
int md = (tl + tr) >> 1;
updater(v + v, psp[v], tl, md);
updater(v + v + 1, psp[v], md + 1, tr);
}
int psr = t[v][2];
t[v][1] = max(t[v][1], (psr < psp[v] ? n - psp[v] + psr : psr - psp[v]));
psp[v] = -1;
}
void com(int v)
{
if (t[v + v][0] == t[v + v + 1][0])
{
if (t[v + v][1] > t[v + v + 1][1]) t[v] = t[v + v];
else t[v] = t[v + v + 1];
}
else
{
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)
{
psp[v] = -1;
if (tl == tr) t[v] = {a[tl], 0, 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), 0, 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 upd(int v, int tl, int tr, int l, int r, int ps)
{
Push(v, tl, tr);
if (tr < l || r < tl || l > r || tl > tr) return;
if (l <= tl && tr <= r) {updater(v, ps, tl, tr); Push(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd(v + v, tl, md, l, r, ps);
upd(v + v + 1, md + 1, tr, l, r, ps);
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);
for (int i = 0; i < n; i++)
if (r[i] == 0)
{
upd(1, 0, n - 1, 0, i - 1, i);
upd(1, 0, n - 1, i + 1, n - 1, i);
}
int cur = n;
while (cur > 0)
{
array <int, 3> b = t[1];
h[b[2]] = cur--;
upd(1, 0, n - 1, b[2]);
upd(1, 0, n - 1, max(0, b[2] - k + 1), b[2] - 1, b[2]);
if (b[2] - k + 1 < 0) upd(1, 0, n - 1, n - abs(b[2] - k + 1), n - 1, b[2]);
}
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;
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, {1, 0, 3, 2, 3, 0, 2});
//
// for (int i = 0; i < 7; i++) cout << h[i] << " ";
//}
