問題文
長さ N の配列 a が与えられます。
1≤l≤r≤N について、f(l,r) を以下のように定義します。
- al,al+1,...,ar が全て異なる場合、f(l,r)=l≤i≤r∑ai
- そうでない場合、f(l,r)=0
Q 個のクエリが与えられます。
i(1≤i≤Q) 個目のクエリでは Li、Ri が与えられるので、それぞれのクエリについて、f(Li,Ri) を求めてください。
制約
- 1≤N,Q≤104
- 1≤ai≤109
- 1≤Li≤Ri≤N
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q
a1 a2 ... aN
L1 R1
L2 R2
... ...
LQ RQ
出力
それぞれのクエリに対する答えを改行区切りで出力せよ。
入出力例
入力例1
5 3
1 2 3 2 1
1 3
2 4
5 5
最初のクエリについて、a1,a2,a3 の値は全て異なるため、それらの和である 6 を出力します。
2 番目のクエリについては、a2,a3,a4 の値に 2 が 2 つ含まれているため、0 を出力します。
3 番目のクエリについては、a5 の値である 1 を出力します。
入力例2
10 5
31415 9 265358 9 7 9 323846264 338327 9 5028841
1 3
1 4
5 8
7 10
1 10
出力例2
296782
0
324184607
329213441
0