#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)2e5 + 100;
int A[N];
int vl[N];
struct Node{
pii valid; // = r + vl
pii zero; // = r
int rlazy;
int vllazy;
};
Node T[N * 4 + 512];
void push(int node, int cl, int cr){
T[node].valid.fi += T[node].rlazy + T[node].vllazy;
T[node].zero.fi += T[node].rlazy;
if(cl != cr){
T[node*2].rlazy += T[node].rlazy;
T[node*2+1].rlazy += T[node].rlazy;
T[node*2].vllazy += T[node].vllazy;
T[node*2+1].vllazy += T[node].vllazy;
}
T[node].rlazy = 0;
T[node].vllazy = 0;
}
void upd(int node, int cl, int cr, int tl, int tr, int typ, int v){
push(node, cl, cr);
if(cr < tl || cl > tr)
return;
if(cl >= tl && cr <= tr){
if(typ == 0) T[node].rlazy = v;
else T[node].vllazy = v;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
upd(node * 2, cl, mid, tl, tr, typ, v);
upd(node * 2 + 1, mid + 1, cr, tl, tr, typ, v);
T[node].valid = min(T[node*2].valid, T[node*2+1].valid);
T[node].zero = min(T[node*2].zero, T[node*2+1].zero);
}
pii get(int node, int cl, int cr, int tl, int tr, int ta){
push(node, cl, cr);
if(cr < tl || cl > tr)
return mp((int)1e9, (int)1e9);
if(cl >= tl && cr <= tr){
if(ta == 0)
return T[node].zero;
else
return T[node].valid;
}
int mid = (cl + cr) / 2;
return min(get(node * 2, cl, mid, tl, tr, ta), get(node * 2 + 1, mid + 1, cr, tl, tr, ta));
}
vector<int> r;
void build(int node, int cl, int cr){
if(cl == cr){
T[node].valid = mp(r[cl], cl);
T[node].zero = mp(r[cl], cl);
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
T[node].valid = min(T[node * 2].valid, T[node * 2 + 1].valid);
T[node].zero = min(T[node * 2].zero, T[node * 2 + 1].zero);
}
int n, k;
void upd_zero(int ii, int sign){
int nx = (ii + k - 1) % n;
if(nx > ii){
upd(1, 0, n - 1, ii + 1, nx, 1, sign);
}
else{
upd(1, 0, n - 1, ii + 1, n - 1, 1, sign);
upd(1, 0, n - 1, 0, nx, 1, sign);
}
}
vector<int> getz(int li, int ri){
vector<int> soln;
pii cc;
while(li <= ri){
cc = get(1, 0, n - 1, li, ri, 0);
if(cc.fi != 0) return soln;
soln.push_back(cc.se);
li = cc.se + 1;
}
return soln;
}
const int LOG = 18;
int lef[LOG][N];
int rig[LOG][N];
int cl[LOG][N];
int cr[LOG][N];
void init(int k_, vector<int> r_) {
r = r_;
k = k_;
n = r.size();
build(1, 0, n - 1);
for(int i = 0 ; i < n; i ++ ){
if(r[i] == 0){
upd_zero(i,+1);
}
}
int st;
int pv;
int nx;
for(int id = n - 1; id >= 0 ; id -- ){
st = T[1].valid.se;
A[st] = id;
pv = (st - (k - 1) + n) % n;
upd(1, 0, n - 1, st, st, 0, (int)1e9);
upd_zero(st,-1);
vector<int> nwz, cc;
if(pv < st){
upd(1, 0, n - 1, pv, st - 1, 0, -1);
cc = getz(pv, st - 1);
for(auto q : cc) nwz.push_back(q);
}
else{
upd(1, 0, n - 1, 0, st - 1, 0, -1);
upd(1, 0, n - 1, pv, n - 1, 0, -1);
cc = getz(0, st - 1);
for(auto q : cc) nwz.push_back(q);
cc = getz(pv, n - 1);
for(auto q : cc) nwz.push_back(q);
}
for(auto x : nwz){
upd_zero(x,+1);
}
}
multiset<pii> alx;
for(int i = n - 1; i >= n - (k - 1); i -- ){
alx.insert(mp(A[i], i));
}
for(int i = 0 ; i < n; i ++ ){
auto it = alx.lower_bound(mp(A[i],-1));
if(it == alx.begin()){
lef[0][i] = -1;
}
else{
it -- ;
cl[0][i] = (it->se > i);
lef[0][i] = it->se;
}
pv = (i - (k - 1) + n) % n;
alx.erase(mp(A[pv], pv));
alx.insert(mp(A[i],i));
}
alx.clear();
for(int i = 1; i < k ; i ++ ){
alx.insert(mp(A[i],i));
}
for(int i = 0; i < n; i ++ ){
auto it = alx.lower_bound(mp(A[i],-1));
if(it == alx.begin()){
rig[0][i] = -1;
}
else{
it -- ;
cr[0][i] = (it->se < i);
rig[0][i] = it->se;
}
if(i < n){
alx.erase(mp(A[i + 1], i + 1));
alx.insert(mp(A[(i + k) % n], (i + k) % n));
}
}
for(int lg = 1; lg < LOG; lg ++ ){
for(int i = 0 ; i < n; i ++ ){
lef[lg][i]=rig[lg][i]=-1;
if(lef[lg-1][i] != -1){
lef[lg][i]=lef[lg-1][lef[lg-1][i]];
cl[lg][i] = (cl[lg-1][i] | cl[lg-1][lef[lg-1][i]]);
}
if(rig[lg-1][i] != -1){
rig[lg][i]=rig[lg-1][rig[lg-1][i]];
cr[lg][i] = (cr[lg-1][i] | cr[lg-1][rig[lg-1][i]]);
}
}
}
}
int compare_plants(int x, int y) {
int go = x;
for(int i = LOG - 1; i >= 0 ; i -- ){
if(lef[i][go] != -1 && cl[i][go] != 1)
go = lef[i][go];
}
if(lef[0][go] != -1){
if(lef[0][go] > y){
go = lef[0][go];
for(int i = LOG - 1; i >= 0 ; i -- ){
if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > y)
go = lef[i][go];
}
if((go - y + n) % n < k){
if(A[go] > A[y]) return +1;
}
}
else{
if(A[go] > A[y]) return +1;
}
}
go = x;
for(int i = LOG - 1; i >= 0 ; i -- ){
if(rig[i][go] != -1 && cr[i][go] != 1 && rig[i][go] < y){
go = rig[i][go];
}
}
if(y - go < k){
if(A[go] > A[y]) return +1;
}
//
go = y;
for(int i = LOG - 1; i >= 0 ; i -- ){
if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > x){
go = lef[i][go];
}
}
if(go - x < k){
if(A[go] > A[x]) return -1;
}
//
go = y;
for(int i = LOG - 1; i >= 0 ; i -- ){
if(rig[i][go] != -1 && cr[i][go] != 1)
go = rig[i][go];
}
if(rig[0][go] != -1){
if(rig[0][go] < x){
for(int i = LOG - 1; i >= 0 ; i -- ){
if(rig[i][go] != -1 && cr[i][go] != 1 && cr[i][go] < x){
go = rig[i][go];
}
}
if(x - go < k){
if(A[go] > A[x]) return -1;
}
}
else{
if(A[go] > A[x]) return -1;
}
}
return 0;
}
