問題
JOI君とビ太郎は冒険の末、一列に並んだ$N$個の宝石を発見した。
調査の結果、左から$i(1 \leq i \leq N)$個目の宝石の値段は$A_i$であることが分かっている。
これらの宝石をJOI君とビ太郎で、次のルールで分けることにした。
1.JOI君が、残りの宝石のうち、左端のものか右端のものを選んで取る。
2.残りの宝石がなくなっていたら、終了する。
3.ビ太郎が、残りの宝石のうち、左端のものと右端のもののうち値段が高い方を取る。
4.残りの宝石があれば1に戻り、なければ終了する。
しかし、$N$個の宝石のうちいくつかが、危険で触れられないものだと発覚したため、危険な宝石を除いて分けることにした。
自分が取れる宝石の値段の総和の最大値が気になったJOI君は、$Q$個のシナリオを想定した。
$j(1 \leq j \leq Q)$番目のシナリオは、「危険ではない宝石は左から$L_j$個目から$R_j$個目までのみである」というものである。
それぞれのシナリオについて、JOI君が得られる宝石の値段の総和の最大値を求めるプログラムを作成せよ。
制約
- $2 \leq N \leq 2000$
- $1 \leq A_i \leq N(1 \leq i \leq N)$
- $A_i≠A_j(i≠j)$
- $1 \leq Q \leq 10^5$
- $1 \leq L_j \leq R_j \leq N(1 \leq j \leq Q)$
- 入力される値はすべて整数である。
小課題
1.(4点)$L_j+1=R_j(1 \leq j \leq Q)$2.(13点)$Q=1$,$A_i=i(1 \leq i \leq N)$
3.(12点)$A_i=i(1 \leq i \leq N)$
4.(19点)$N \leq 20$,$Q=1$
5.(29点)$Q \leq 10$
6.(23点)追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ $...$ $A_N$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $...$ $L_Q$ $R_Q$
出力
標準出力に$Q$行出力せよ。$j(1 \leq j \leq Q)$行目には、$j$番目のシナリオにおいてJOI君が得られる宝石の値段の総和の最大値を出力せよ。
出力の最後に改行を入れること。
入出力例
入力例1
7 1 2 3 4 5 6 7 3 1 3 4 5 1 7
出力例1
4 5 16
1つ目のシナリオについて、JOI君が左から3番目の宝石→ビ太郎が左から2番目の宝石→JOI君が左から1番目の宝石、の順に取ることで、得た宝石の値段の総和を4にすることが出来る。
2つ目のシナリオについて、JOI君は左から5番目の宝石のみを取ることで、得た宝石の値段の総和を5にすることが出来る。
3つ目のシナリオについて、左から1,3,5,7番目の宝石を取るように行動することが可能で、この時の得た宝石の値段の総和は16である。得た宝石の値段の総和を17以上にすることはできないので16を出力する。
この入出力例は小課題$3,4,5,6$の制約を満たす。
入力例2
5 1 2 3 4 5 1 3 4
出力例2
4
この入出力例はすべての小課題の制約を満たす。
入力例3
21 6 8 7 13 12 15 17 4 20 19 3 2 1 16 18 9 21 14 5 11 10 11 7 11 11 15 3 9 8 21 13 20 4 19 7 14 13 21 7 17 2 5 1 4
出力例3
40 22 52 79 51 99 42 56 70 21 21
この入出力例は小課題$6$の制約を満たす。