AT_arc180_d [ARC180D] Division into 3

[problemUrl]: https://atcoder.jp/contests/arc180/tasks/arc180_d 長さ $ N $ の整数列 $ A=(A_1,A_2,\cdots,A_N) $ が与えられます． 以下の $ Q $ 個のクエリに答えてください． - $ i $ 番目のクエリ: 整数 $ L_i,R_i $ が与えられる． $ B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i}) $ に対して次の問題を解け． - $ B $ を $ 3 $ つの非空な連続部分列に分割する．各連続部分列についてその要素の最大値を求める．これらの値の総和としてあり得る最小値を求めよ． なお，問題の制約から $ B $ の長さは $ 3 $ 以上になるため，$ 3 $ つの非空な連続部分列に分割する方法は必ず $ 1 $ つ以上存在する．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ．$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ．

### 制約 - $ 3\ \leq\ N\ \leq\ 250000 $ - $ 1\ \leq\ Q\ \leq\ 250000 $ - $ 1\ \leq\ A_i\ \leq\ 10^8 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ R_i-L_i\ \geq\ 2 $ - 入力される値はすべて整数 ### Sample Explanation 1 $ 1 $ つめのクエリについて説明します． $ B=(4,3,1,1,4,5,2) $ です． これを $ (4,3),(1,1),(4,5,2) $ と分解すると，各連続部分列の最大値は $ 4,1,5 $ となり，その総和は $ 10 $ になります． この総和が $ 10 $ より小さくなる方法は存在しないので，このクエリの答えは $ 10 $ になります．