#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long ll;
struct segTree{
pair<int, int> tree[1600002];
int lazy[1600002];
void init(int i, int l, int r, int *A){
lazy[i] = 0;
if(l==r){
tree[i] = make_pair(A[l], l);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
void propagate(int i, int l, int r){
tree[i].first += lazy[i];
if(l!=r){
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
}
lazy[i] = 0;
}
void add(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
add(i*2, l, m, s, e, val);
add(i*2+1, m+1, r, s, e, val);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
pair<int, int> findMin(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return make_pair(INT_MAX, INT_MAX);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(findMin(i*2, l, m, s, e), findMin(i*2+1, m+1, r, s, e));
}
} tree;
int n, k;
int NODE;
bool dist(int x, int y){
x = (x+1 - NODE + n*10) % n;
y = (y+1 - NODE + n*10) % n;
if((x<k) ^ (y<k)) return y<k;
return x<y;
}
struct mineSeg{
struct Node {
int lmax; int lidx;
int rmax; int ridx;
int ans; int ansl, ansr;
int sum;
Node(){}
Node(ll x, int idx){
lmax = rmax = ans = sum = x;
lidx = ridx = ansl = ansr = idx;
}
Node merge(const Node &r)const{
Node ret = *this;
if(ret.lmax < sum + r.lmax){
ret.lmax = sum + r.lmax;
ret.lidx = r.lidx;
}
ret.rmax += r.sum;
if(ret.rmax < r.rmax || (ret.rmax == r.rmax && dist(ret.ridx, r.ridx))){
ret.rmax = r.rmax;
ret.ridx = r.ridx;
}
if(ret.ans < r.ans || (ret.ans == r.ans && dist(ret.ansr, r.ansr))){
ret.ans = r.ans, ret.ansl = r.ansl, ret.ansr = r.ansr;
}
if(ret.ans < rmax + r.lmax || (ret.ans == rmax+r.lmax && dist(ret.ansr, r.lidx))){
ret.ans = rmax + r.lmax;
ret.ansl = ridx, ret.ansr = r.lidx;
}
ret.sum += r.sum;
ret.sum = max(ret.sum, (int)-1e9);
return ret;
}
} tree[1600002];
void init(int i, int l, int r, int *A){
if(l==r){
tree[i] = Node(A[l] ? 1 : -1e9, l);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = tree[i*2].merge(tree[i*2+1]);
}
void change(int i, int l, int r, int idx, int x){
if(l==r){
tree[i] = Node(x ? 1 : -1e9, l);
return;
}
int m = (l+r)>>1;
if(idx <= m) change(i*2, l, m, idx, x);
else change(i*2+1, m+1, r, idx, x);
tree[i] = tree[i*2].merge(tree[i*2+1]);
}
} mineTree;
int arr[400002];
int sum[400002];
int ans[400002];
vector<int> bigger[5002];
void init(int _k, vector<int> r) {
n = (int)r.size();
k = _k;
for(int i=1; i<=n; i++) arr[i] = r[i-1];
for(int i=n+1; i<=n*2; i++) arr[i] = arr[i-n];
for(int c=1; c<=n; c++){
NODE = c;
tree.init(1, 1, n*2, arr);
mineTree.init(1, 1, n*2, arr);
for(int turn=n; turn>=1; turn--){
if(tree.findMin(1, 1, n*2, c, c).first == 0) break;
auto tmp = mineTree.tree[1];
if(tmp.ans < k-1) exit(1);
int loc = tmp.ansr % n + 1;
if(loc == c) break;
bigger[c].push_back(loc);
/// 1에서 0이 되는 위치들을 검색
int lim = loc+n, leftmost = lim-k+1;
while(leftmost < lim){
pair<int, int> tmp2 = tree.findMin(1, 1, n*2, leftmost, lim-1);
if(tmp2.first > 1) break;
int x = tmp2.second;
mineTree.change(1, 1, n*2, (x-1)%n+1, 0);
mineTree.change(1, 1, n*2, (x-1)%n+1+n, 0);
leftmost = x+1;
}
mineTree.change(1, 1, n*2, loc, 1);
mineTree.change(1, 1, n*2, loc+n, 1);
/// tree 변경
tree.add(1, 1, n*2, loc, loc, 1000000000);
tree.add(1, 1, n*2, loc+n, loc+n, 1000000000);
if(loc >= k){
tree.add(1, 1, n*2, loc-k+1, loc, -1);
tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
}
else{
tree.add(1, 1, n*2, 1, loc, -1);
tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
tree.add(1, 1, n*2, 2*n-(k-loc)+1, n*2, -1);
}
}
for(int i=c+n-1; i>=c+n-k+1; i--){
if(tree.findMin(1, 1, n*2, i, i).first) continue;
int loc = (i-1)%n+1;
bigger[c].push_back(loc);
/// tree 변경
tree.add(1, 1, n*2, loc, loc, 1000000000);
tree.add(1, 1, n*2, loc+n, loc+n, 1000000000);
if(loc >= k){
tree.add(1, 1, n*2, loc-k+1, loc, -1);
tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
}
else{
tree.add(1, 1, n*2, 1, loc, -1);
tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
tree.add(1, 1, n*2, 2*n-(k-loc)+1, n*2, -1);
}
}
}
}
int compare_plants(int x, int y) {
x++, y++;
if(find(bigger[x].begin(), bigger[x].end(), y) != bigger[x].end()) return -1;
if(find(bigger[y].begin(), bigger[y].end(), x) != bigger[y].end()) return 1;
return 0;
}
