問題文

長さ $N$ の配列 $a$ が与えられます。
$1 \leq l \leq r \leq N$ について、$f(l, r)$ を以下のように定義します。

• $a_l, a_{l+1},...,a_r$ が全て異なる場合、$f(l, r) = \displaystyle \sum_{l \leq i \leq r} a_i$
• そうでない場合、$f(l, r) = 0$

$Q$ 個のクエリが与えられます。
$i \: (1 \leq i \leq Q)$ 個目のクエリでは $L_i$、$R_i$ が与えられるので、それぞれのクエリについて、$f(L_i, R_i)$ を求めてください。

制約

• $1 \leq N, Q \leq 10^4$
• $1 \leq a_i \leq 10^9$
• $1 \leq L_i \leq R_i \leq N$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
a1 a2 ... aN
L1 R1
L2 R2
... ...
LQ RQ

出力

それぞれのクエリに対する答えを改行区切りで出力せよ。

入出力例

5 3
1 2 3 2 1
1 3
2 4
5 5

6
0
1

最初のクエリについて、$a_1, a_2, a_3$ の値は全て異なるため、それらの和である $6$ を出力します。
$2$ 番目のクエリについては、$a_2, a_3, a_4$ の値に $2$ が $2$ つ含まれているため、$0$ を出力します。
$3$ 番目のクエリについては、$a_5$ の値である $1$ を出力します。

10 5
31415 9 265358 9 7 9 323846264 338327 9 5028841
1 3
1 4
5 8
7 10
1 10

296782
0
324184607
329213441
0