{"raw_statement":[{"iden":"statement","content":"_a_ is an array of _n_ positive integers, all of which are not greater than _n_.\n\nYou have to process _q_ queries to this array. Each query is represented by two numbers _p_ and _k_. Several operations are performed in each query; each operation changes _p_ to _p_ + _a__p_ + _k_. There operations are applied until _p_ becomes greater than _n_. The answer to the query is the number of performed operations."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 100000).\n\nThe second line contains _n_ integers — elements of _a_ (1 ≤ _a__i_ ≤ _n_ for each _i_ from 1 to _n_).\n\nThe third line containts one integer _q_ (1 ≤ _q_ ≤ 100000).\n\nThen _q_ lines follow. Each line contains the values of _p_ and _k_ for corresponding query (1 ≤ _p_, _k_ ≤ _n_)."},{"iden":"output","content":"Print _q_ integers, _i_th integer must be equal to the answer to _i_th query."},{"iden":"example","content":"Input\n\n3\n1 1 1\n3\n1 1\n2 1\n3 1\n\nOutput\n\n2\n1\n1"},{"iden":"note","content":"Consider first example:\n\nIn first query after first operation _p_ = 3, after second operation _p_ = 5.\n\nIn next two queries _p_ is greater than _n_ after the first operation."}],"translated_statement":[{"iden":"statement","content":"#cf_span[a] 是一个包含 #cf_span[n] 个正整数的数组，所有元素均不超过 #cf_span[n]。\n\n你需要对这个数组处理 #cf_span[q] 个查询。每个查询由两个数 #cf_span[p] 和 #cf_span[k] 表示。每个查询中会执行若干次操作；每次操作将 #cf_span[p] 更新为 #cf_span[p + ap + k]。这些操作会持续进行，直到 #cf_span[p] 大于 #cf_span[n]。该查询的答案是执行的操作次数。\n\n第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 100000)]。\n\n第二行包含 #cf_span[n] 个整数 —— 数组 #cf_span[a] 的元素（对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n]，满足 #cf_span[1 ≤ ai ≤ n]）。\n\n第三行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 100000)]。\n\n接下来 #cf_span[q] 行，每行包含对应查询的 #cf_span[p] 和 #cf_span[k] 的值 #cf_span[(1 ≤ p, k ≤ n)]。\n\n请输出 #cf_span[q] 个整数，第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。\n\n考虑第一个例子：\n\n在第一个查询中，第一次操作后 #cf_span[p = 3]，第二次操作后 #cf_span[p = 5]。\n\n在接下来的两个查询中，第一次操作后 #cf_span[p] 就已大于 #cf_span[n]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 100000)]。第二行包含 #cf_span[n] 个整数 —— 数组 #cf_span[a] 的元素（对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n]，满足 #cf_span[1 ≤ ai ≤ n]）。第三行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 100000)]。接下来 #cf_span[q] 行，每行包含对应查询的 #cf_span[p] 和 #cf_span[k] 的值 #cf_span[(1 ≤ p, k ≤ n)]。"},{"iden":"output","content":"请输出 #cf_span[q] 个整数，第 #cf_span[i] 个整数必须等于第 #cf_span[i] 个查询的答案。"},{"iden":"note","content":"考虑第一个例子：在第一个查询中，第一次操作后 #cf_span[p = 3]，第二次操作后 #cf_span[p = 5]。在接下来的两个查询中，第一次操作后 #cf_span[p] 就已大于 #cf_span[n]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of array $ a = (a_1, a_2, \\dots, a_n) $, where $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number of queries.  \nEach query is a pair $ (p, k) \\in \\{1, \\dots, n\\}^2 $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100000 $  \n2. $ 1 \\leq q \\leq 100000 $  \n3. $ 1 \\leq a_i \\leq n $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\leq p, k \\leq n $ for each query  \n\n**Objective**  \nFor each query $ (p, k) $, define the sequence $ p_0 = p $, and for $ t \\geq 0 $:  \n$$ p_{t+1} = p_t + a_{p_t} + k $$  \nLet $ T $ be the smallest non-negative integer such that $ p_T > n $.  \nOutput $ T $.","simple_statement":null,"has_page_source":false}