{"problem":{"name":"[JOIST 2023] 比太郎之旅 / Bitaro's Travel","description":{"content":"在 JOI 市有一条很长的道路，可以看作是实数轴。道路上的一个位置由一个实数坐标表示。在 JOI 市，沿着这条道路有 $N$ 个观光景点，按坐标递增的顺序编号为 $1$ 到 $N$。第 $i$ 个观光景点 $(1 \\le i \\le N)$ 的坐标为 $X_i$。 Bitaro 将参观 JOI 市的所有观光景点。由于“贪婪”是他生活的口号，他将重复以下步骤，直到参观完所有的观光景点。 - 设 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9342"},"statements":[{"statement_type":"Markdown","content":"在 JOI 市有一条很长的道路，可以看作是实数轴。道路上的一个位置由一个实数坐标表示。在 JOI 市，沿着这条道路有 $N$ 个观光景点，按坐标递增的顺序编号为 $1$ 到 $N$。第 $i$ 个观光景点 $(1 \\le i \\le N)$ 的坐标为 $X_i$。\n\nBitaro 将参观 JOI 市的所有观光景点。由于“贪婪”是他生活的口号，他将重复以下步骤，直到参观完所有的观光景点。\n\n- 设 $x$ 为 Bitaro 当前的坐标。在他尚未参观的观光景点中，选择一个景点 $i$，使得从 Bitaro 当前坐标到该景点的距离 $|x - X_i|$ 最小。然后 Bitaro 移动到景点 $i$ 的位置，并参观它。如果有多个这样的观光景点，他会移动到坐标较小的那个景点。这里，$|t|$ 是 $t$ 的绝对值。\n\n然而，由于多年的经验，Bitaro 知道如果他通过重复上述步骤来移动，总旅行距离可能会比他预期的要长。由于总旅行距离会根据起始坐标的不同而变化，他想知道如果从 $Q$ 个起始坐标候选 $S_1, S_2, \\dots, S_Q$ 中的每一个开始，直到参观完所有观光景点的总旅行距离。\n\n为了帮助 Bitaro，编写一个程序，计算如果他从每个起始坐标候选开始的总旅行距离，给定 JOI 市的信息和起始坐标候选。\n\n## Input\n\n从标准输入读取以下数据。\n\n> $N$\n> \n> $X_1\\ X_2\\cdots X_N$\n> \n> $Q$\n> \n> $S_1$\n> \n> $S_2$\n> \n> $\\vdots$\n> \n> $S_Q$\n\n## Output\n\n向标准输出写入 $Q$ 行。输出的第 $j$ 行 $(1 \\le j \\le Q)$ 应包含如果 Bitaro 从坐标 $S_j$ 开始的总旅行距离。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n如果 Bitaro 从坐标 $7$ 开始，他将按如下方式参观所有观光景点。\n1. 他尚未参观的观光景点有 $1, 2, 3, 4, 5$，从 Bitaro 当前坐标到这些景点的距离分别为 $7, 2, 1, 0, 2$。由于观光景点 $4$ 是离 Bitaro 最近的景点，他停留在坐标 $7$ 并参观观光景点 $4$。\n2. 他尚未参观的观光景点有 $1, 2, 3, 5$，从 Bitaro 当前坐标到这些景点的距离分别为 $7, 2, 1, 2$。由于观光景点 $3$ 是离 Bitaro 最近的景点，他从坐标 $7$ 移动到坐标 $6$ 并参观观光景点 $3$。\n3. 他尚未参观的观光景点有 $1, 2, 5$，从 Bitaro 当前坐标到这些景点的距离分别为 $6, 1, 3$。由于观光景点 $2$ 是离 Bitaro 最近的景点，他从坐标 $6$ 移动到坐标 $5$ 并参观观光景点 $2$。\n4. 他尚未参观的观光景点有 $1, 5$，从 Bitaro 当前坐标到这些景点的距离分别为 $5, 4$。由于观光景点 $5$ 是离 Bitaro 最近的景点，他从坐标 $5$ 移动到坐标 $9$ 并参观观光景点 $5$。\n5. 他尚未参观的观光景点有 $1$。由于观光景点 $1$ 是离 Bitaro 最近的景点，他从坐标 $9$ 移动到坐标 $0$ 并参观观光景点 $1$。\n\n由于 Bitaro 的总旅行距离是 $15$，输出 $15$。\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #2】**\n\n该样例满足子任务 $3, 4$ 的限制。\n\n**【数据范围】**\n\n对于所有测试数据，满足 $1 \\le N, Q \\le 2 \\times 10^5$，$0 \\le X_i \\le 10^9$，$X_i < X_{i+1}$，$0 \\le S_j \\le 10^9$，保证所有输入均为整数。\n\n|子任务编号|分值|限制|\n|:-:|:-:|:-:|\n|$1$|$5$|$Q=1, N \\le 2 \\times 10^3$|\n|$2$|$10$|$Q=1$|\n|$3$|$30$|$X_{i+1} - X_i \\le 100$|\n|$4$|$55$|无|\n\n题面翻译由 ChatGPT-4o 提供。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9342","tags":["2023","JOISC/JOIST（日本）"],"sample_group":[["5\n0 5 6 7 9\n1\n7\n","15"],["10\n1 2 3 4 5 6 7 8 9 10\n10\n1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n","9\n10\n11\n12\n13\n14\n15\n16\n17\n9\n"]],"created_at":"2026-03-03 11:09:25"}}