問題文

define 君は 4 月にオープンする遊園地「パ研ランド」の設計をしています。この遊園地は東西に細長いことが特徴で、その入口は遊園地の最も西にあります。以下、入口から東に k m 進んだ場所を地点 k と呼ぶことにします。

この遊園地にはアトラクションが N 基 あり、 1, 2, \dots, N の番号が振られています。アトラクション i は地点 i にあります。

define 君はパ研ランドのオープン日にぺんぎん君を招待しています。ぺんぎん君は 1m 進むのに 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 を結ぶワープ路を造った時にぺんぎん君の計画に掛かる移動時間は何秒か」というものです。それぞれのクエリに答えてください。

制約

• 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

5 6
3 5 2 1 5 3
2
1 3
2 5

出力例 1

11
8

クエリ 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

10 10
3 1 4 1 2 9 3 2 7 10 
10
1 7
1 4
3 8
6 9
3 4
1 8
7 10
4 10
3 5
6 9

出力例 2

24
27
21
27
31
23
29
25
28
27

この入力例は全ての小課題の制約を満たします。

入力例 3

100 20
6 97 94 50 96 51 94 86 92 77 9 73 21 9 46 42 76 77 49 17 
20
38 87
20 60
5 56
8 82
69 80
13 42
90 99
97 98
96 97
95 97
61 88
48 61
11 73
42 81
8 18
78 83
17 54
41 68
2 69
72 100

出力例 3

401
451
449
417
573
489
625
633
633
631
493
535
401
393
596
609
451
467
437
543

この入力例は小課題 1,3,4,5,6 の制約を満たします。

原案: define