AT_joig2026final_e.鉄道旅行 4 (Railway Trip 4)

ローマのとある郊外に， $ 1 $ 本の十分に長い線路がある．この線路は数直線とみなすことができ，線路沿いの各地点は $ 1 $ 個の整数による座標で表される． この線路に沿って $ N $ 個の駅があり，座標の小さい順に $ 1 $ から $ N $ までの番号が付けられている．駅 $ i $ ( $ 1 \leqq i \leqq N $ ) の位置は座標 $ A_i $ である． $ 2 $ つ以上の駅が同じ座標に存在することはない．

この線路上を列車が走っている．列車は座標が小さい地点から大きい地点に向かう方向にのみ運行しており，すべての駅に停車する．

運賃は乗車駅と降車駅の距離に応じて決まり，ある整数列 $ (B_1, B_2, ..., B_K) $ を用いて以下のように計算される．ここで， $ 1 = B_1 < B_2 < \cdots < B_K $ が成り立つ．なお，乗車駅と降車駅は相異なる必要がある．

• 乗車駅と降車駅の距離を $ d $ ( $ d\geqq 1 $ ) とし， $ B_j \leqq d $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) を $ j_\text{max} $ とする．このとき，運賃は $ j_\text{max} $ である．

イタリア観光に来たビ太郎は，この列車に $ Q $ 回乗車する計画があり，各回の運賃を計算しようと思っている． $ k $ 回目 ( $ 1 \leqq k \leqq Q $ ) の乗車計画では，列車に乗って駅 $ l_k $ から駅 $ r_k $ まで行きたいと思っている．ここで， $ l_k < r_k $ である．

ビ太郎は疲れているので，列車に乗らず駅の間を移動することはしない．しかし，途中下車して運賃を一度精算し，再度その駅から乗車することはできる． 途中下車はどの駅でも可能であり，回数に制限はない． 例えば，駅 $ s_1, s_2, \cdots, s_m $ で途中下車した場合 ( $ l_k < s_1 < s_2 < \cdots < s_m < r_k $ )，距離 $ A_{s_1} - A_{l_k}, A_{s_2} - A_{s_1}, A_{s_3} - A_{s_2}, \cdots, A_{s_m} - A_{s_{m-1}}, A_{r_k} - A_{s_m} $ の分の運賃を支払うことになる．

ビ太郎は適切に途中下車することで，駅 $ l_k $ から駅 $ r_k $ まで行くのに必要な運賃の合計を最小化したい．

駅と運賃と乗車計画の情報が与えられたとき，それぞれの乗車計画について，ビ太郎が支払う必要のある運賃の合計の最小値を求めるプログラムを作成せよ．

---

入力は以下の形式で標準入力から与えられる．

$ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_{N} $ $ K $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_{K} $ $ Q $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_Q $ $ r_Q $

標準出力に $ Q $ 行出力せよ． $ k $ 行目 ( $ 1 \leqq k \leqq Q $ ) には $ k $ 回目の乗車計画についてビ太郎が支払う必要のある運賃の合計の最小値を出力せよ．

---

小課題

1. ( $ 8 $ 点) $ K \leqq 2 $ ．
2. ( $ 11 $ 点) $ N \leqq 500 $ ．
3. ( $ 29 $ 点) $ Q = 1 $ ．
4. ( $ 20 $ 点) $ K \leqq 5 $ ．
5. ( $ 32 $ 点) 追加の制約はない．

---

Sample Explanation 1

$ 1 $ 回目の乗車計画では，ビ太郎は列車に乗って駅 $ l_1=1 $ から駅 $ r_1=5 $ まで行きたいと思っている． このとき，例えば以下のように行動することができる．

• まず，駅 $ 1 $ で乗車し，駅 $ 3 $ で途中下車する．このときの乗車距離は $ A_3 - A_1 = 3 $ であり， $ B_j \leqq 3 $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) は $ 2 $ であるので，運賃は $ 2 $ である．
• 次に，駅 $ 3 $ で再度乗車し，駅 $ 5 $ で降車する．このときの乗車距離は $ A_5 - A_3 = 4 $ であり， $ B_j \leqq 4 $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) は $ 2 $ であるので，運賃は $ 2 $ である．

この場合の運賃の合計は $ 2 + 2 = 4 $ であり，これより運賃の合計を小さくすることはできない．よって， $ 1 $ 行目に $ 4 $ を出力する．

$ 2 $ 回目の乗車計画では，ビ太郎は列車に乗って駅 $ l_2=3 $ から駅 $ r_2=5 $ まで行きたいと思っている． このとき，例えば以下のように行動することができる．

• 駅 $ 3 $ で乗車し，駅 $ 5 $ で下車する．このときの乗車距離は $ A_5 - A_3 = 4 $ であり， $ B_j \leqq 4 $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) は $ 2 $ であるので，運賃は $ 2 $ である．

この場合の運賃の合計は $ 2 $ であり，これより運賃の合計を小さくすることはできない．よって， $ 2 $ 行目に $ 2 $ を出力する．

$ 3 $ 回目の乗車計画では，ビ太郎は列車に乗って駅 $ l_3=1 $ から駅 $ r_3=7 $ まで行きたいと思っている． このとき，例えば以下のように行動することができる．

• まず，駅 $ 1 $ で乗車し，駅 $ 4 $ で途中下車する．このときの乗車距離は $ A_4 - A_1 = 4 $ であり， $ B_j \leqq 4 $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) は $ 2 $ であるので，運賃は $ 2 $ である．
• 次に，駅 $ 4 $ で再度乗車し，駅 $ 6 $ で途中下車する．このときの乗車距離は $ A_6 - A_4 = 4 $ であり， $ B_j \leqq 4 $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) は $ 2 $ であるので，運賃は $ 2 $ である．
• 次に，駅 $ 6 $ で再度乗車し，駅 $ 7 $ で降車する．このときの乗車距離は $ A_7 - A_6 = 3 $ であり， $ B_j \leqq 3 $ を満たす最大の整数 $ j $ ( $ 1 \leqq j \leqq K $ ) は $ 2 $ であるので，運賃は $ 2 $ である．

この場合の運賃の合計は $ 2 + 2 + 2 = 6 $ であり，これより運賃の合計を小さくすることはできない．よって， $ 3 $ 行目に $ 6 $ を出力する．

この入力例は小課題 $ 2,5 $ の制約を満たす．

---

Sample Explanation 2

この入力例はすべての小課題の制約を満たす．

---

Sample Explanation 3

この入力例は小課題 $ 2,5 $ の制約を満たす．

Constraints

• $ 2 \leqq N \leqq 150,000 $ ．
• $ 1 \leqq A_1 < A_2 < \cdots < A_N \leqq 10^9 $ ．
• $ 1 \leqq K \leqq 20 $ ．
• $ 1 = B_1 < B_2 < \cdots < B_K \leqq 10^9 $ ．
• $ 1 \leqq Q \leqq 150,000 $ ．
• $ 1 \leqq l_k < r_k \leqq N $ ( $ 1 \leqq k \leqq Q $ )．
• 入力される値はすべて整数である．