#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXLOG = 19;
struct SparseTable {
vector<vector<int>> st;
vector<int> logs;
void build(const vector<int>& a) {
int n = a.size();
logs.assign(n + 1, 0);
for (int i = 2; i <= n; i++) logs[i] = logs[i / 2] + 1;
st.assign(MAXLOG, vector<int>(n));
for (int i = 0; i < n; i++) st[0][i] = a[i];
for (int j = 1; j < MAXLOG; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r) {
if (l > r) return -1;
int j = logs[r - l + 1];
return max(st[j][l], st[j][r - (1 << j) + 1]);
}
};
vector<int> solve(vector<int> &v, vector<int> &w, vector<pair<int, int>> &queries) {
int n = v.size();
vector<int> next1(n);
for (int i = 0; i < n; i++) next1[i] = min(n - 1, i + v[i]);
SparseTable st1;
st1.build(next1);
// up[k][i] - макс. позиция за 2 * 2^k крови
vector<vector<int>> up(MAXLOG, vector<int>(n));
for (int i = 0; i < n; i++) {
int best_after_1 = st1.query(i, next1[i]);
up[0][i] = max(best_after_1, min(n - 1, i + w[i]));
}
for (int k = 1; k < MAXLOG; k++) {
for (int i = 0; i < n; i++) {
up[k][i] = up[k - 1][up[k - 1][i]];
}
}
vector<int> results;
for (auto &q : queries) {
int A = q.first, B = q.second;
if (A >= B) {
results.push_back(0);
continue;
}
// Если можно дойти за 1 шаг
if (A + v[A] >= B) {
results.push_back(1);
continue;
}
int curr = A;
int total_cost = 0;
// Прыгаем степенями двойки по 2 капли
for (int k = MAXLOG - 1; k >= 0; k--) {
if (up[k][curr] < B) {
curr = up[k][curr];
total_cost += (1 << (k + 1));
}
}
// Сейчас curr < B, но за следующий прыжок стоимостью 2 мы точно попадем в B (или дальше)
// Проверяем, нельзя ли закончить за 1 каплю
if (curr + v[curr] >= B) {
total_cost += 1;
} else {
total_cost += 2;
}
results.push_back(total_cost);
}
return results;
}
