#include "jumps.h"
#include <vector>
using namespace std;
const int N = 200000;
typedef vector<int> vi;
int max(int a, int b) { return a > b ? a : b; }
int ll[N], rr[N], qu[N], n;
void init(int n_, vi hh) {
int i, cnt;
n = n_;
cnt = 0;
for (i = 0; i < n; i++) {
while (cnt && hh[qu[cnt - 1]] < hh[i])
cnt--;
ll[i] = cnt == 0 ? -1 : qu[cnt - 1];
qu[cnt++] = i;
}
cnt = 0;
for (i = n - 1; i >= 0; i--) {
while (cnt && hh[qu[cnt - 1]] < hh[i])
cnt--;
rr[i] = cnt == 0 ? -1 : qu[cnt - 1];
qu[cnt++] = i;
}
}
int dd[N];
int minimum_jumps(int i1, int j1, int i2, int j2) {
if (n > N)
return i2 - j1;
else {
int head, cnt, i;
for (i = 0; i < n; i++)
dd[i] = n;
head = cnt = 0;
for (i = i1; i <= j1; i++)
dd[i] = 0, qu[head + cnt++] = i;
while (cnt) {
int d;
i = qu[cnt--, head++], d = dd[i] + 1;
if (i2 <= i && i <= j2)
return dd[i];
if (ll[i] != -1 && dd[ll[i]] > d)
dd[ll[i]] = d, qu[head + cnt++] = ll[i];
if (rr[i] != -1 && dd[rr[i]] > d)
dd[rr[i]] = d, qu[head + cnt++] = rr[i];
}
return -1;
}
}
