{"problem":{"name":"E. Jumping","description":{"content":"Shopping with the wife is one of men's hardest marriage responsibilities. Nour is a good husband. So he goes out with his wife every Friday to \"Damasquino\" mall.  Damasquino is a very famous mall in ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10114E"},"statements":[{"statement_type":"Markdown","content":"Shopping with the wife is one of men's hardest marriage responsibilities. Nour is a good husband. So he goes out with his wife every Friday to \"Damasquino\" mall. \n\nDamasquino is a very famous mall in Damascus. It has a very unique transportation method between shops. Since the shops in the mall are laying in a straight line, you can jump on a very advanced trampoline from the shop i, and land in shop (i + di) or (i - di) depending on the direction of the jump. Where di is a constant given for each shop. You can jump forward or backward only, and you can't land any where before the first shop or after the last shop in the mall.\n\nThere are N shops in the mall, numbered from 1 to N. Nour's wife starts her shopping journey from shop 1 and ends it in shop N. Unfortunately, Nour sometimes gets lost from his wife (the mall is very crowded on Fridays). So he wants to know for each shop, what is the minimum number of trampoline jumps he has to make in order to reach shop N and see his wife again!\n\nThe first line consists of one integer T, the number of test cases. \n\nEach test case consists of two lines, the first line contains a single integer (2 ≤ N ≤ 105) the number of shops in the mall. The second line contains N integers. Where the ith integer (1 ≤ di ≤ N) is the constant described above for the ith shop.\n\nFor each test case, print N lines. The ith line should contain one integer, the minimum number of jumps needed to be made in order to reach shop N starting from shop i, or  - 1 if it is impossible. \n\nLarge I/O files. Please consider using fast input/output methods.\n\n## Input\n\nThe first line consists of one integer T, the number of test cases. Each test case consists of two lines, the first line contains a single integer (2 ≤ N ≤ 105) the number of shops in the mall. The second line contains N integers. Where the ith integer (1 ≤ di ≤ N) is the constant described above for the ith shop.\n\n## Output\n\nFor each test case, print N lines. The ith line should contain one integer, the minimum number of jumps needed to be made in order to reach shop N starting from shop i, or  - 1 if it is impossible. \n\n[samples]\n\n## Note\n\nLarge I/O files. Please consider using fast input/output methods.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $, $ 2 \\leq N \\leq 10^5 $, denote the number of shops.  \n- Let $ d = (d_1, d_2, \\dots, d_N) $, where $ d_i \\in \\mathbb{Z} $ and $ 1 \\leq d_i \\leq N $, be the jump constant for shop $ i $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{large} $ (implied by large I/O).  \n2. For each shop $ i \\in \\{1, \\dots, N\\} $:  \n   - From shop $ i $, a jump of length $ d_i $ is allowed to shop $ i + d_i $ (forward) or $ i - d_i $ (backward).  \n   - Jumps must land within bounds: $ 1 \\leq \\text{target} \\leq N $.  \n\n**Objective**  \nFor each shop $ i \\in \\{1, \\dots, N\\} $, compute the minimum number of jumps required to reach shop $ N $, starting from shop $ i $.  \nIf unreachable, output $ -1 $.  \n\nFormally, define $ f(i) $ as the minimum number of jumps from shop $ i $ to shop $ N $.  \nThen:  \n$$\nf(i) = \n\\begin{cases}\n0 & \\text{if } i = N \\\\\n\\min \\left( \\left\\{ f(i + d_i) + 1 \\mid i + d_i \\leq N \\right\\} \\cup \\left\\{ f(i - d_i) + 1 \\mid i - d_i \\geq 1 \\right\\} \\right) & \\text{if at least one valid jump exists} \\\\\n\\infty & \\text{otherwise}\n\\end{cases}\n$$  \nOutput $ f(i) $ for $ i = 1 $ to $ N $, with $ \\infty \\rightarrow -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10114E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}