AT_pakencamp_2021_day3_f ワープ

[problemUrl]: https://atcoder.jp/contests/pakencamp-2021-day3/tasks/pakencamp_2021_day3_f define 君は 4 月にオープンする遊園地「パ研ランド」の設計をしています。この遊園地は東西に細長いことが特徴で、その入口は遊園地の最も西にあります。以下、入口から東に $ k $ m 進んだ場所を地点 $ k $ と呼ぶことにします。 この遊園地にはアトラクションが $ N $ 基 あり、 $ 1,\ 2,\ \dots,\ N $ の番号が振られています。アトラクション $ i $ は地点 $ i $ にあります。 define 君はパ研ランドのオープン日にぺんぎん君を招待しています。ぺんぎん君は $ 1 $m 進むのに $ 1 $ 秒掛かります。ぺんぎん君は $ M $ 回に渡ってアトラクションに乗る計画を立てており、$ i $ 番目に乗るのはアトラクション $ A_i $ と決めています。 この計画では、地点 $ A_i $ から地点 $ A_{i+1} $ への移動に掛かる最短時間を $ T_i $ 秒として、移動に $ \sum_{i=1}^{M-1}{T_i} $ 秒掛かります。 さて、オープン直前になって define 君は「アトラクションが一列に並んでいると移動しにくいのでは？」と思い始めました。このままでは、ぺんぎん君が途中で移動が嫌になって帰ってしまうかもしれません。 そこで、時間もないので $ 1 $ 本だけワープ路を造る事にしました。地点を $ 2 $ つ選んでワープ路を造ると、その $ 2 $ 地点間を双方向に $ 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\