#include "plants.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N;
vvi lift;
void init(int k, std::vector<int> r)
{
assert(k == 2);
N = sz(r);
lift.assign(N, vi(ceil(log2(N) + 1)));
for (int i = 0; i < N; ++i)
lift[i][0] = (r[i] == 1) ? 1 : -1;
for (int j = 1; j < sz(lift[0]); ++j)
{
for (int i = 0; i < N; ++i)
{
if (lift[i][j - 1] == 0 || lift[i][j - 1] != lift[(i + (1 << (j - 1))) % N][j - 1])
lift[i][j] = 0;
else
lift[i][j] = lift[i][j - 1];
}
}
return;
}
int compare_helper(int x, int y)
{
assert(x < y);
int initial = lift[x % N][0];
for (int j = sz(lift[x % N]); j >= 0; --j)
{
int nx = x + (1 << j);
if (nx > y)
continue;
if (lift[x % N][j] != initial)
return 0;
x = nx;
}
return -1 * initial;
}
int compare_plants(int x, int y)
{
int factor = 1;
if (x > y)
swap(x, y), factor *= -1;
int tmp = factor * compare_helper(x, y);
if (tmp != 0)
return tmp;
factor *= -1;
return factor * compare_helper(y, x + N);
}
