#include <bits/stdc++.h>
using namespace std;
#define F0R(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b - 1;i>=a;i--)
template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int,int>;
const int INF=1e9+7;
map<tuple<int,int,int,int>, int> cash;
int query(int a, int b, int x, int y);
int query2(int a, int b, int x, int y) {
if (a < x) {
swap(a,x);
swap(b,y);
}
if (cash.count({a,b,x,y}))
return cash[{a,b,x,y}];
return cash[{a,b,x,y}] = query(a,b,x,y);
}
int search(int l, int r) {
int testL = l, testR = r;
bool dir = true;
int tries = max((int)log2(r - l), 10);
int space = tries;
if (r - l >= space * 2) {
bool s1 = query2(l,l + space - 1, l, r - 1);
bool s2 = query2(r - space, r - 1, l, r - 1);
if (s2 and !s1) dir = false;
if (!s2 and !s2) return -1;
}
while (testR > testL and tries-- > 0) {
if (dir) {
if (query2(testL, testL, l, r - 1)) {
return testL;
}
testL++;
} else {
testR--;
if (query2(testR, testR, l, r - 1)) {
return testR;
}
}
}
exit(5);
}
int searchBinary(int a, int b) {
int l = a, r = b;
while (l < r) {
int mid = l + (r - l) / 2; // Including MID
if (query2(l, mid, a,b - 1)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
int solve(int l, int r, int* L, int* R) {
if (r - l == 1) {
L[l] = -1;
R[l] = -1;
return l;
}
if (r - l == 0) return -1;
int mid = search(l, r);
if (mid == -1)
mid = searchBinary(l, r);
L[mid] = solve(l, mid, L, R);
if (mid < r - 1)
R[mid] = solve(mid + 1, r, L, R);
else R[mid] = -1;
return mid;
}
int solve(int N, int* L, int* R) {
cash.clear();
return solve(0, N, L, R);
}
#if DEBUG
vi s;
int query(int a, int b, int x, int y) {
int gcd1 = s[a], gcd2 = s[x];
FOR(i, a, b + 1)
gcd1 = gcd(gcd1, s[i]);
FOR(i, x, y + 1)
gcd2 = gcd(gcd2, s[i]);
return gcd1 == gcd2;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
s.resize(n);
F0R(i, n) cin >> s[i];
int* l = new int[n];
int* r = new int[n];
solve(n, l, r);
int stop = 25;
F0R(i, n) {
cout << l[i] << " " << r[i] << endl;
}
return 0;
}
#endif
#if DEBUG2
int queries = 0;
vi s;
int query(int a, int b, int x, int y) {
int gcd1 = s[a], gcd2 = s[x];
FOR(i, a, b + 1)
gcd1 = gcd(gcd1, s[i]);
FOR(i, x, y + 1)
gcd2 = gcd(gcd2, s[i]);
queries++;
return gcd1 == gcd2;
}
int rand(int a, int b) {
return rand() % (b - a + 1) + a;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n = 100;
s.resize(n);
vi p(n);
FOR(i, 1, n) {
p[i] = rand(0, i);
}
vi prime(1e4, true);
vi primeList;
FOR(i, 2, prime.size()) {
if (!prime[i]) continue;
primeList.push_back(prime[i]);
prime[i] = false;
for (int j = i; j < prime.size(); j+=i) {
prime[j] = false;
}
}
int iter = 0;
s[0] = 2;
FOR(i, 1, n) {
s[i] = s[p[i]] * primeList[iter++];
}
int* l = new int[n];
int* r = new int[n];
solve(n, l, r);
int stop = 25;
cout << queries << endl;
return 0;
}
#endif
