#include <iostream>
#include <algorithm>
#include <numeric>
#include "popa.h"
using namespace std;
int const MAXNN=1e3+10;
// int s[MAXNN]={};
int lc[MAXNN],rc[MAXNN],pr[MAXNN],sf[MAXNN];
// bool query(int a,int b,int c,int d)
// {
// int g=0,g1=0;
// for (int i=a;i<=b;i++)
// g=gcd(g,s[i]);
// for (int i=c;i<=d;i++)
// g1=gcd(g1,s[i]);
// return (g==g1);
// }
int sol(int l,int r)
{
if (l>r)
return -1;
if (l==r)
return l;
for (int i=l;i<=r;i++)
{
if (pr[i]<=l&&sf[i]>=r)
{
lc[i]=sol(l,i-1);
rc[i]=sol(i+1,r);
return i;
}
}
return -1;
}
int solve(int N,int* left,int* right)
{
for (int i=0;i<N;i++)
lc[i]=rc[i]=-1;
for (int i=0;i<N;i++)
{
{
int st=-1,en=i;
while (st+1<en)
{
int mid=(st+en)/2;
if (query(mid,i,i,i))
en=mid;
else
st=mid;
}
pr[i]=en;
}
{
int st=i,en=N;
while (st+1<en)
{
int mid=(st+en)/2;
if (query(i,mid,i,i))
st=mid;
else
en=mid;
}
sf[i]=st;
}
}
int rt=sol(0,N-1);
for (int i=0;i<N;i++)
left[i]=lc[i],right[i]=rc[i];
return rt;
}
// int main()
// {
// int n;
// cin>>n;
// for (int i=0;i<n;i++)
// cin>>s[i];
// int l[n],r[n];
// cout<<solve(n,l,r)<<endl;
// for (int i=0;i<n;i++)
// cout<<l[i]<<' '<<r[i]<<endl;
// }
