#include "plants.h"
#include <stdio.h>
#include <vector>
#include <utility>
#include <set>
using namespace std;
vector < int > all;
vector < int > Next[200005];
vector < pair < int , int > > con[200005];
int N,tt=0;
bool use[2000005]={0};
int Con[200005];
int what[200005];
int now=1;
struct A
{
int l,r;
int nxl,nxr;
int small1,small2;
int add1,add2;
}Node[2000005];
void build(int l,int r,int here)
{
Node[here].l=l;
Node[here].r=r;
Node[here].add1=0;
Node[here].add2=0;
Node[here].small1=0;
if(l==r)
{
Node[here].small2=all[l];
return ;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
}
void UPD(int here)
{
Node[Node[here].nxl].add1+=Node[here].add1;
Node[Node[here].nxl].small1+=Node[here].add1;
Node[Node[here].nxr].add1+=Node[here].add1;
Node[Node[here].nxr].small1+=Node[here].add1;
Node[here].add1=0;
}
void cha1(int l,int r,int con,int here)
{
if(l>r) return ;
if(l==Node[here].l&&r==Node[here].r)
{
Node[here].add1+=con;
Node[here].small1+=con;
return;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxr);
else
{
cha1(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
cha1((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
}
Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
}
int Find(int where,int here)
{
if(Node[here].l==where&&Node[here].r==where) return Node[here].small1;
if(where<=(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxl);
else return Find(where,Node[here].nxr);
}
void init(int k,vector<int> r)
{
int a=0,b=0,i,j,ok=0,l,t,t2,x;
all=r;
N=r.size();
if(k==2) tt=1;
for(i=0;i<N;i++)
{
if(k==2)
{
if(r[(i+N-1)%N]!=r[i])
{
b=0;
a++;
con[i].push_back(make_pair(a,0));
for(j=(i+1)%N;r[(j+N-1)%N]==r[i];j=(j+1)%N)
{
if(j==N-1) ok=1;
if(r[i]==0) b--;
else b++;
con[j].push_back(make_pair(a,b));
}
}
}
else
{
for(i=0;i<N;i++)
{
if(r[i]==0)
{
t=(i+k-1)%N;
if(t>=i) cha1(i+1,t,1,0);
else
{
cha1(i+1,N-1,1,0);
cha1(0,t,1,0);
}
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(use[j]==0&&Find(j,0)==0&&r[j]==0)
{
x=j;
break;
}
}
what[x]=i;
use[x]=1;
t=(x+k-1)%N;
if(t>=x) cha1(x+1,t,1,0);
else
{
cha1(x+1,N-1,1,0);
cha1(0,t,1,0);
}
for(j=1;j<k;j++)
{
t=(x-j+2*N)%N;
r[t]--;
if(r[t]==0)
{
t2=(t+k-1)%N;
if(t2>=t) cha1(t+1,t2,1,0);
else
{
cha1(t+1,N-1,1,0);
cha1(0,t2,1,0);
}
}
}
}
}
}
return;
}
bool F(int A,int B)
{
if(A==B) return 1;
if(use[A]) return 0;
use[A]=1;
for(auto i:Next[A]) if(F(i,B)) return 1;
return 0;
}
int compare_plants(int x, int y)
{
int i;
if(tt)
{
for(auto i:con[x])
{
for(auto j:con[y])
{
if(i.first==j.first)
{
if(i.second<j.second) return -1;
return 1;
}
}
}
}
else
{
if(what[x]<what[y]) return 1;
else return -1;
}
return 0;
}
