#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include<set>
#include<algorithm>
using namespace std;
vector<int> g[200005], arr;
int n, l[18][200005], r[18][200005], j[18][200005], idx[200005];
int mx(int a, int b) {
if ((a == -1) || (b == -1)) return max(a, b);
return ((arr[a] > arr[b]) ? a : b);
}
void init(int tn, vector<int> a) {
n = tn, arr = a;
for (int i = 0; i < n; ++i)
idx[arr[i]] = i;
memset(l, -1, sizeof(l));
memset(r, -1, sizeof(r));
memset(j, -1, sizeof(j));
vector<int> q;
for (int i = 0; i < n; ++i) {
while (q.size() && (q.back() < arr[i])) q.pop_back();
if (q.size()) l[0][i] = idx[q.back()];
q.push_back(arr[i]);
}
q.clear();
for (int i = n - 1; i >= 0; --i) {
while (q.size() && (q.back() < arr[i])) q.pop_back();
if (q.size()) r[0][i] = idx[q.back()];
q.push_back(arr[i]);
}
for (int i = 0; i < n; ++i)
j[0][i] = mx(l[0][i], r[0][i]);
for (int x = 1; x < 18; ++x)
for (int i = 0; i < n; ++i) {
l[x][i] = ((l[x - 1][i] == -1) ? -1 : l[x - 1][l[x - 1][i]]);
r[x][i] = ((r[x - 1][i] == -1) ? -1 : r[x - 1][r[x - 1][i]]);
j[x][i] = ((j[x - 1][i] == -1) ? -1 : j[x - 1][j[x - 1][i]]);
}
}
int minimum_jumps(int a, int b, int c, int d) {
if (arr[b] > arr[c]) return -1;
int ans = 0;
for (int i = 17; i >= 0; --i)
if (j[i][b] != -1)
if (arr[j[i][b]] <= arr[c])
ans += (1 << i), b = j[i][b];
if (b == c) return ans;
if (r[0][b] <= arr[c]) {
for (int i = 17; i >= 0; --i)
if (r[i][b] != -1)
if (arr[r[i][b]] <= arr[c])
ans += (1 << i), b = r[i][b];
}
else
for (int i = 17; i >= 0; --i)
if (l[i][b] != -1)
if (arr[l[i][b]] <= arr[c])
ans += (1 << i), b = l[i][b];
if (b == c) return ans;
return -1;
}
/*int main()
{
init(15, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 });
for(int i = 0; i < 15; ++i)
for (int j = i + 1; j < 15; ++j) {
int res = minimum_jumps(i, i, j, j);
if (res != (j - i)) {
cout << "Fail: " << i << " " << j;
return 0;
}
}
cout << "Success!";
}*/
