{"problem":{"name":"Tak and Hotels","description":{"content":"$N$ hotels are located on a straight line. The coordinate of the $i$\\-th hotel $(1 \\leq i \\leq N)$ is $x_i$. Tak the traveler has the following two personal principles: *   He never travels a distanc","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc060_c"},"statements":[{"statement_type":"Markdown","content":"$N$ hotels are located on a straight line. The coordinate of the $i$\\-th hotel $(1 \\leq i \\leq N)$ is $x_i$.\nTak the traveler has the following two personal principles:\n\n*   He never travels a distance of more than $L$ in a single day.\n*   He never sleeps in the open. That is, he must stay at a hotel at the end of a day.\n\nYou are given $Q$ queries. The $j$\\-th $(1 \\leq j \\leq Q)$ query is described by two distinct integers $a_j$ and $b_j$. For each query, find the minimum number of days that Tak needs to travel from the $a_j$\\-th hotel to the $b_j$\\-th hotel following his principles. It is guaranteed that he can always travel from the $a_j$\\-th hotel to the $b_j$\\-th hotel, in any given input.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq L \\leq 10^9$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq x_i < x_2 < ... < x_N \\leq 10^9$\n*   $x_{i+1} - x_i \\leq L$\n*   $1 \\leq a_j,b_j \\leq N$\n*   $a_j \\neq b_j$\n*   $N,\\,L,\\,Q,\\,x_i,\\,a_j,\\,b_j$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $x_2$ $...$ $x_N$\n$L$\n$Q$\n$a_1$ $b_1$\n$a_2$ $b_2$\n:\n$a_Q$ $b_Q$\n\n## Partial Score\n\n*   $200$ points will be awarded for passing the test set satisfying $N \\leq 10^3$ and $Q \\leq 10^3$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc060_c","tags":[],"sample_group":[["9\n1 3 6 13 15 18 19 29 31\n10\n4\n1 8\n7 3\n6 7\n8 5","4\n2\n1\n2\n\nFor the $1$\\-st query, he can travel from the $1$\\-st hotel to the $8$\\-th hotel in $4$ days, as follows:\n\n*   Day $1$: Travel from the $1$\\-st hotel to the $2$\\-nd hotel. The distance traveled is $2$.\n*   Day $2$: Travel from the $2$\\-nd hotel to the $4$\\-th hotel. The distance traveled is $10$.\n*   Day $3$: Travel from the $4$\\-th hotel to the $7$\\-th hotel. The distance traveled is $6$.\n*   Day $4$: Travel from the $7$\\-th hotel to the $8$\\-th hotel. The distance traveled is $10$."]],"created_at":"2026-03-03 11:01:14"}}