#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define INF 2e18
#define MOD 1e9+7
struct Node{
Node * left, * right; ll ind;
Node(ll _ind):ind(_ind){
left=right=nullptr;
}
};
// ll cnt; vector<ll> a;
// bool query(ll l1, ll r1, ll l2, ll r2){
// cnt++;
// ll gcd1 = 0, gcd2=0;
// for (ll i=l1; i<=r1; i++) gcd1=__gcd(gcd1, a[i]);
// for (ll i=l2; i<=r2; i++) gcd2=__gcd(gcd2, a[i]);
// return (gcd1==gcd2);
// }
void dfs(Node * cur, int *Left, int *Right){
Left[cur->ind] = (cur->left?cur->left->ind:-1);
Right[cur->ind] = (cur->right?cur->right->ind:-1);
if (cur->left) dfs(cur->left, Left, Right);
if (cur->right) dfs(cur->right, Left, Right);
}
int solve(ll n, int *Left, int *Right){
Node * cur = new Node(0);
vector<Node*> chain; chain.push_back(cur);
Node * temp; Node * buffer;
for (ll i=1; i<n; i++){
if (query(chain.back()->ind, i, chain.back()->ind, chain.back()->ind)){
temp = new Node(i);
chain.back()->right=temp;
chain.push_back(temp);
}else{
temp = new Node(i);
while (!chain.empty() and query(i, i, chain.back()->ind, i)){
buffer = chain.back();
chain.pop_back();
}
temp->left = buffer;
if (!chain.empty()) chain.back()->right=temp;
chain.push_back(temp);
}
}
dfs(chain[0], Left, Right);
return chain[0]->ind;
}
// void solve(){
// cnt=0; ll n; cin >> n; a.resize(n);
// for (ll i=0; i<n; i++) cin >> a[i];
// int Left[n], Right[n];
// solve(n, Left, Right);
// for (ll i=0; i<n; i++){
// cout << Left[i] << " ";
// }
// cout << ln;
// for (ll i=0; i<n; i++){
// cout << Right[i] << " ";
// }
// cout << ln;
// }
// int main(){
// ios_base::sync_with_stdio(false); cin.tie(nullptr);
// auto start = chrono::high_resolution_clock::now();
// ll t=1;
// // cin >> t;
// while (t--) solve();
// #ifdef LOCAL
// auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
// cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
// #endif
// }
