新 JOI 通りには $N$ 個のビルが左から右に一列に並んでいる．左から $i$ 番目のビル (以下，ビル $i$ と記す) の高さは $H_i$ キロメートルであり，隣り合うビルはちょうど $1$ キロメートル離れている．各ビルには $1$ 人の住人が屋上に住んでおり，全員秒速 $1$ キロメートル
で歩くことができる．

この通りでは，今年は $Q$ 個の会議が開催される予定である．$i$ 個目の会議では，ビル $L_i,\ L_i+1\ ,\ ...\ ,\ R_i$ の住民が一つのビル $x\ (L_i ≤ x ≤ R_i)$ に集まらなければならない．会議をできるだけ迅速に進めるため，「集まる時間」が最短となるようなビル $x$ を選ぶことにした．
「集まる時間」は以下のように定義される．

「集まる時間」は会議の参加者のうち最も移動に時間を要する住人の移動時間である．
ただし，ビル $t$ の住人がビル $x$ に移動するときにかかる時間は，次式で表される．

$H_t +|t − x| + H_x$

ここでは，ビル $x$ の住人も移動しなければならないことに注意せよ．

各会議における，最短の「集まる時間」をそれぞれ求めよ．

• $1 ≤ T ≤ 3$
• $2 ≤ N ≤ 200\ 000$
• $1 ≤ Q ≤ 200\ 000$
• $1 ≤ H_i ≤ 200\ 000$
• $1 ≤ L_i ≤ R_i ≤ N$
• 入力はすべて整数である．

この課題は，8 個の小課題から成る．
ただし，小課題 6 の制約，入力全体についての制約ではなく，各テストケースについての制約であることに注意せよ．

各入力データ について，以下の形式で入力が与えられる．

$T$
(1 個目のテストケースの情報)
(2 個目のテストケースの情報)
...
($T$ 個目のテストケースの情報)

各テストケースについて，以下の形式で入力が与えられる.

• 1 行目に，整数 $N, Q$ が空白区切りで与えられる.
• 2 行目に，整数 $H_1, H_2, H_3, ... , H_N$ が空白区切りで与えられる.
• $2 + i\ (1 ≤ i ≤ Q)$ 行目に，整数 $L_i,R_i$ が空白区切りで与えられる.

出力

$T$ 行に渡って出力せよ.
$i$ 行目には，$i$ 個目のテストケースにおける答えを,以下の通りに出力せよ．

$ans_j$ を， $j$ 個目の会議における「集まる時間」の最小値とする．
そのとき， $ans_1, ans_2, ... , ans_Q$を空白区切りで出力せよ．