#include "plants.h"
#include <stdio.h>
#include <vector>
#include <utility>
#include <set>
using namespace std;
vector < int > all;
vector < int > ttt;
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;
int con=0,con1;
}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;
Node[here].con=0;
Node[here].con1=0;
if(l==r)
{
Node[here].small2=all[l];
Node[here].con1=1;
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);
if(Node[Node[here].nxl].small2==Node[here].small2) Node[here].con1+=Node[Node[here].nxl].con1;
if(Node[Node[here].nxr].small2==Node[here].small2) Node[here].con1+=Node[Node[here].nxr].con1;
}
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;
Node[Node[here].nxl].add2+=Node[here].add2;
Node[Node[here].nxl].small2+=Node[here].add2;
Node[Node[here].nxr].add2+=Node[here].add2;
Node[Node[here].nxr].small2+=Node[here].add2;
Node[here].add2=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);
if(Node[Node[here].nxl].small2==Node[here].small2) Node[here].con1+=Node[Node[here].nxl].con1;
if(Node[Node[here].nxr].small2==Node[here].small2) Node[here].con1+=Node[Node[here].nxr].con1;
}
void cha2(int l,int r,int con,int here)
{
if(l>r) return ;
if(l==Node[here].l&&r==Node[here].r)
{
Node[here].add2+=con;
Node[here].small2+=con;
return;
}
UPD(here);
if(r<=(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxr);
else
{
cha2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
cha2((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);
if(Node[Node[here].nxl].small2==Node[here].small2) Node[here].con1+=Node[Node[here].nxl].con1;
if(Node[Node[here].nxr].small2==Node[here].small2) Node[here].con1+=Node[Node[here].nxr].con1;
}
int Find1(int where,int here)
{
if(Node[here].l==where&&Node[here].r==where) return Node[here].small1;
UPD(here);
if(where<=(Node[here].l+Node[here].r)/2) return Find1(where,Node[here].nxl);
else return Find1(where,Node[here].nxr);
}
int Find2(int where,int here)
{
if(Node[here].l==where&&Node[here].r==where) return Node[here].small2;
UPD(here);
if(where<=(Node[here].l+Node[here].r)/2) return Find2(where,Node[here].nxl);
else return Find2(where,Node[here].nxr);
}
void New(int here)
{
if(Node[here].l==Node[here].r)
{
ttt.push_back(Node[here].l);
Node[here].con++;
return;
}
UPD(here);
if(Node[Node[here].nxl].con!=Node[Node[here].nxl].con1&&Node[Node[here].nxl].small2==0) New(Node[here].nxl);
if(Node[Node[here].nxr].con!=Node[Node[here].nxr].con1&&Node[Node[here].nxr].small2==0) New(Node[here].nxr);
Node[here].con=Node[Node[here].nxl].con+Node[Node[here].nxr].con;
}
void init(int k,vector<int> r)
{
int a=0,b=0,i,j,ok=0,l,t,t2,x,ll,rr;
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
{
build(0,N-1,0);
ttt.clear();
New(0);
for(auto t:ttt)
{
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);
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(use[j]==0&&Find1(j,0)==0&&Find2(j,0)==0)
{
x=j;
break;
}
}
//printf("aa %d\n",x);
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);
}
ll=(x-(k-1)+N)%N;
rr=(x-1+N)%N;
if(rr>=ll) cha2(ll,rr,-1,0);
else
{
cha2(ll,N-1,-1,0);
cha2(0,rr,-1,0);
}
ttt.clear();
New(0);
for(auto t:ttt)
{
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;
}
