#include <bits/stdc++.h>
// #include <stack>
// #include <queue>
// #include <limits>
// #include <climits>
// #include <math.h>
using namespace std;
constexpr int N = 2e5 + 5;
constexpr int logN = static_cast<int>(log2(N));
template <typename T>
inline T mymin(T x, T y) {
return x < y ? x : y;
}
template <typename T>
inline T mymax(T x, T y) {
return x > y ? x : y;
}
#define min mymin
#define max mymax
int n, q;
int *h;
int Next[N], Prev[N];
int highUp[logN + 1][N];
int lowUp[logN + 1][N];
int prevUp[logN + 1][N];
int nextUp[logN + 1][N];
int minTable[logN + 1][N];
pair<int, int> maxTable[logN + 1][N];
template <auto f, auto st>
void buildSparseTable() {
for (int k = 1; k <= logN; k++) {
for (int i = 0; i + (1 << k) <= n; i++)
st[k][i] = f(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
template <auto up>
void buildUpTable() {
for (int k = 0; k < logN; k++) {
for (int i = 0; i <= n; i++)
up[k + 1][i] = up[k][up[k][i]];
}
}
template <auto f, auto st>
auto query(int l, int r) {
int k = 31 - __builtin_clz(r - l);
return f(st[k][l], st[k][r - (1 << k)]);
}
int query(int a, int b, int c) {
int res = 0;
for (int k = logN; k >= 0; k--) {
if (prevUp[k][b] < a || h[prevUp[k][b]] > h[c]) continue;
b = prevUp[k][b];
}
for (int k = logN; k >= 0; k--) {
if (h[highUp[k][b]] > h[c]) continue;
b = highUp[k][b];
res += 1 << k;
}
for (int k = logN; k >= 0; k--) {
if (h[lowUp[k][b]] > h[c]) continue;
b = lowUp[k][b];
res += 1 << k;
}
if (b != c) {
return -1;
}
return res;
}
int rquery(int a, int b, int c) {
int res = 0;
for (int k = logN; k >= 0; k--) {
if (nextUp[k][a] > b || h[nextUp[k][a]] > h[c]) continue;
a = nextUp[k][a];
}
for (int k = logN; k >= 0; k--) {
if (h[highUp[k][a]] > h[c]) continue;
a = highUp[k][a];
res += 1 << k;
}
for (int k = logN; k >= 0; k--) {
if (h[lowUp[k][a]] > h[c]) continue;
a = lowUp[k][a];
res += 1 << k;
}
if (a != c) {
return -1;
}
return res;
}
void init(int N, int *H) {
n = N;
h = H;
h[n] = N;
stack<int> stk;
stk.push(n);
for (int i = 0; i < n; i++) {
while (h[stk.top()] <= h[i]) {
stk.pop();
}
Prev[i] = stk.top();
stk.push(i);
}
while (!stk.empty()) stk.pop();
stk.push(n);
for (int i = n - 1; i >= 0; i--) {
while (h[stk.top()] <= h[i]) {
stk.pop();
}
Next[i] = stk.top();
stk.push(i);
}
for (int i = 0; i < n; i++) {
highUp[0][i] = h[Next[i]] < h[Prev[i]] ? Prev[i] : Next[i];
lowUp[0][i] = h[Next[i]] < h[Prev[i]] ? Next[i] : Prev[i];
prevUp[0][i] = Prev[i];
nextUp[0][i] = Next[i];
}
highUp[0][n] = n;
lowUp[0][n] = n;
prevUp[0][n] = n;
nextUp[0][n] = n;
buildUpTable<highUp>();
buildUpTable<lowUp>();
buildUpTable<prevUp>();
buildUpTable<nextUp>();
for (int i = 0; i < n; i++) {
minTable[0][i] = h[i];
maxTable[0][i] = {h[i], i};
}
buildSparseTable<min<int>, minTable>();
buildSparseTable<max<pair<int, int>>, maxTable>();
}
int query(int a, int b, int c, int d) {
if (c == d) {
return query(a, b, c);
}
int minsource = query<min<int>, minTable>(a, b + 1);
int maxdest = query<max<pair<int, int>>, maxTable>(c, d + 1).first;
if (h[b] > maxdest) {
for (int k = logN; k >= 0; k--) {
if (b - (1 << k) < a || minTable[k][b - (1 << k) + 1] <= maxdest) continue;
b -= 1 << k;
}
}
if (minsource > maxdest || h[b] > maxdest) {
return -1;
}
if (b + 1 == c) {
return 1;
}
int newa = b + 1;
for (int k = logN; k >= 0; k--) {
if (newa - (1 << k) < a || maxTable[k][newa - (1 << k)].first >= maxdest) continue;
newa -= 1 << k;
}
a = newa;
int maxsource = query<max<pair<int, int>>, maxTable>(a, b + 1).first;
int x = query<max<pair<int, int>>, maxTable>(b + 1, c).second;
if (h[x] > maxdest) {
return -1;
}
if (maxsource > h[x]) {
return 1;
}
int ans = query(a, b, x);
if (Prev[x] < a && h[Prev[x]] < maxdest) {
ans = min<unsigned int>(ans, rquery(a, b, Prev[x]));
}
return ans == -1 ? -1 : ans + 1;
}
