Distinct Sum (Query Version)

2 secs 1024 MB
dyktr_06's icon dyktr_06

問題文

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

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

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

制約

  • 1N,Q1041 \leq N, Q \leq 10^4
  • 1ai1091 \leq a_i \leq 10^9
  • 1LiRiN1 \leq L_i \leq R_i \leq 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
出力例1
6
0
1

最初のクエリについて、a1,a2,a3a_1, a_2, a_3 の値は全て異なるため、それらの和である 66 を出力します。
22 番目のクエリについては、a2,a3,a4a_2, a_3, a_4 の値に 2222 つ含まれているため、00 を出力します。
33 番目のクエリについては、a5a_5 の値である 11 を出力します。

入力例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

提出


Go (1.21)