AT_pakencamp_2021_day3_f ワープ

define 君正在设计一个将在 4 月开放的游乐园“パ研ランド”。这个游乐园的特点是东西方向狭长，入口位于游乐园最西端。以下将距离入口向东 $k$ 米的位置称为地点 $k$。 这个游乐园有 $N$ 个游乐设施，编号为 $1, 2, \dots, N$。游乐设施 $i$ 位于地点 $i$。 define 君邀请了ぺんぎん君在开园当天前来。ぺんぎん君每前进 $1$ 米需要 $1$ 秒。他计划乘坐 $M$ 次游乐设施，第 $i$ 次乘坐的是编号为 $A_i$ 的游乐设施。在这个计划中，从地点 $A_i$ 移动到地点 $A_{i+1}$ 所需的最短时间为 $T_i$ 秒，总共需要 $\sum_{i=1}^{M-1}{T_i}$ 秒完成所有移动。 然而，在开园前夕，define 君开始担心“如果游乐设施都排成一列，会不会不方便移动？”这样下去，ぺんぎん君可能会因为中途移动太麻烦而回家。因此，时间紧迫下，他决定只建造一条“传送通道”。选择两个地点建造传送通道后，可以在这两个地点之间双向以 $1$ 秒的时间移动。 现在有 $Q$ 个询问。第 $i$ 个询问是：“如果在地点 $S_i$ 和地点 $T_i$ 之间建造一条传送通道，ぺんぎん君完成计划所需的移动时间是多少秒？”请回答每个询问。

输入以如下格式从标准输入给出，所有数均为整数。 > $N\ M$ > $A_1\ A_2\ \dots\ A_M$ > $Q$ > $S_1\ T_1$ > $\vdots$ > $S_Q\ T_Q$

请输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 限制条件 - $2 \leq N, M \leq 300000$ - $1 \leq Q \leq 300000$ - $1 \leq A_i \leq N\ (1 \leq i \leq M)$ - $A_i \neq A_{i+1}\ (1 \leq i \leq M-1)$ - $1 \leq S_i < T_i \leq N\ (1 \leq i \leq Q)$ ### 小子任务 1. ($20$ 分) $M, Q \leq 5000$ 2. ($50$ 分) $N \leq 300,\ |A_i - A_{i+1}| \leq 10\ (1 \leq i \leq M-1)$ 3. ($100$ 分) $N \leq 300$ 4. ($280$ 分) $N \leq 2000$ 5. ($300$ 分) $M, Q \leq 50000$ 6. ($50$ 分) 无额外限制。 ### 样例解释 1 在第 2 个询问中，ぺんぎん君可以按如下方式移动： 1. 从地点 $3$ 移动到地点 $2$（$1$ 秒） 2. 使用传送通道从地点 $2$ 移动到地点 $5$（$1$ 秒） 3. 使用传送通道从地点 $5$ 移动到地点 $2$（$1$ 秒） 4. 从地点 $2$ 移动到地点 $1$（$1$ 秒） 5. 从地点 $1$ 移动到地点 $2$（$1$ 秒） 6. 使用传送通道从地点 $2$ 移动到地点 $5$（$1$ 秒） 7. 从地点 $5$ 移动到地点 $3$（$2$ 秒） 请注意，ぺんぎん君总是以最短时间移动。本输入样例满足所有小子任务的限制条件。 ### 样例解释 2 本输入样例满足所有小子任务的限制条件。 ### 样例解释 3 本输入样例满足小子任务 1、3、4、5、6 的限制条件。 原案: [define](https://atcoder.jp/users/define) 由 ChatGPT 4.1 翻译